std::sort function compile error

[9hX8C542]

So, I'm supposed to use different sorting functions and and compare the times in microseconds to each other, to see which one is faster.

The problem is that std::sort keeps failing, and the error code isn't that easy to read. If someone could help me out with this, that would be great. I'll take any help that I can get.

#include <iostream>
#include <chrono>
#include <algorithm>
#include <functional>
#include <array>

using namespace std::chrono;

void swap(int* a, int* b);

template <class T>
void selectionSort(T arr[], T n);

template <class T>
void bubbleSort(T arr[], T n);

template <class T>
void merge(T arr[], T l, T m, T r);
template <class T>
void mergeSort(T arr[], T l, T r);

template <class T>
int partition (T arr[], T low, T high);
template <class T>
void quickSort(T arr[], T low, T high);

template <class T>
void heapify(T arr[], T n, T i);
template <class T>
void heapSort(T arr[], T n);

void test(const unsigned int size);


int main()
{
    test(60000);
    
}//main

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

template <class T>
void selectionSort(T arr[], T n)
{
    T i, j, min_idx;
  
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
            min_idx = j;
  
        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}//functin selectionSort

template <class T>
void bubbleSort(T arr[], T n)
{
    T i, j;
    for (i = 0; i < n-1; i++)
      
    // Last i elements are already in place
    for (j = 0; j < n-i-1; j++)
        if (arr[j] > arr[j+1])
            swap(&arr[j], &arr[j+1]);
}//function bubbleSort

template <class T>
void merge(T arr[], T l, T m, T r)
{
    T i, j, k;
    T n1 = m - l + 1;
    T n2 =  r - m;
  
    /* create temp arrays */
    T L[n1], R[n2];
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
  
    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}//function merge
  
/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
template <class T>
void mergeSort(T arr[], T l, T r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        T m = l+(r-l)/2;
  
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
  
        merge(arr, l, m, r);
    }
}//function mergeSort

template <class T>
int partition (T arr[], T low, T high)
{
    T pivot = arr[high]; // pivot
    T i = (low - 1); // Index of smaller element
  
    for (T j = low; j <= high - 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}//function partition

template <class T>
void quickSort(T arr[], T low, T high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place */
        T pi = partition(arr, low, high);
  
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}//function quickSort

template <class T>
void heapify(T arr[], T n, T i)
{
    T largest = i; // Initialize largest as root
    T l = 2*i + 1; // left = 2*i + 1
    T r = 2*i + 2; // right = 2*i + 2
  
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
  
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
  
    // If largest is not root
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
  
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}//function heapify

template <class T>
void heapSort(T arr[], T n)
{
    // Build heap (rearrange array)
    for (T i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
  
    // One by one extract an element from heap
    for (T i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(&arr[0], &arr[i]);
  
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}//function heapSort


void test(const unsigned int size)
{
    srand(time(NULL));
    
    int array[size];
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startSS = high_resolution_clock::now();
    selectionSort <int>(array, size);
    auto stopSS = high_resolution_clock::now();
    auto durationSelection = duration_cast<microseconds>(stopSS - startSS);
    //
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startBS = high_resolution_clock::now();
    bubbleSort <int>(array, size);
    auto stopBS = high_resolution_clock::now();
    auto durationBubble = duration_cast<microseconds>(stopBS - startBS);
    //
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startMG = high_resolution_clock::now();
    mergeSort <int>(array, array[0], array[size-1]);
    auto stopMG = high_resolution_clock::now();
    auto durationMerge = duration_cast<microseconds>(stopMG - startMG);
    //
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startQS = high_resolution_clock::now();
    quickSort <int>(array, array[0], array[size-1]);
    auto stopQS = high_resolution_clock::now();
    auto durationQuick = duration_cast<microseconds>(stopQS - startQS);
    //
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startHP = high_resolution_clock::now();
    heapSort <int>(array, size);
    auto stopHP = high_resolution_clock::now();
    auto durationHeap = duration_cast<microseconds>(stopHP - startHP);
    //
    
    for (int i = 0; i < size; i++)
    {
        array[i] = rand() % size;
    }
    
    //
    auto startSort = high_resolution_clock::now();
    std::sort(array[0], array[size-1]);
    auto stopSort = high_resolution_clock::now();
    auto durationSort = duration_cast<microseconds>(stopSort - startSort);
    
    
    std::cout << size << " | "
              << durationSelection.count() << " "
              << durationBubble.count()  << " "
              << durationMerge.count() << " "
              << durationQuick.count() << " "
              << durationHeap.count() << " "
              << durationSort.count() << " "
              << std::endl;
    
}//function sixtyTest 

[jonnin]

you need to pass pointers.

std::sort(arr, arr+size);

[9hX8C542]

Oh shit it worked bro, thanks for that quick reply

[jonnin]

you are welcome.

no shell :( all the profs hate shell...

[dhayden]

To get it to run, change line 304 to
std::sort(array, array+size);

What makes you think that your sort algorithms work correctly? When I add code to check the order, it says that mergeSort and quickSort aren't working:

void check(int arr[], unsigned size, const char *name)
{
    for (unsigned i=1; i<size; ++i) {
        if (arr[i] < arr[i-1]) {
            std::cout << "array out of order on " << name << '\n';
            return;
        }
    }
    std::cout << name << " is okay" << std::endl;
}

Then change each call to a sort function to be like this:

    auto startSS = high_resolution_clock::now();
    selectionSort <int>(array, size);
    auto stopSS = high_resolution_clock::now();
    auto durationSelection = duration_cast<microseconds>(stopSS - startSS);
    check(array, size, "selectionSort");

Also, your templates won't work for anything except an int:

template <class T>
void selectionSort(T arr[], T n);

Suppose I have an array of class Dog:
Dog myDogs[12];
To call selectionSort on an array of Dog, I have to pass a Dog as parameter n. Which dog should I pass?

And within selection sort I see:

    T i, j, min_idx;
    ...
    for (i = 0; i < n-1; i++)

My Dog class won't let you assign an int to a Dog. So this won't work.

Also, I see you calling swap() but you've only defined a swap() function for ints.