0

I am repurposing a quick sort program to work for any type of array, but I am running into memory issues. Here is the program for reference:

#include <iostream>

template <class T> void printArray( T *ptr, T max );
template <class T> void swap ( T& a, T& b );
template <class T> T returnPartition ( T array[], T start, T end );
template <class T> void quickSort( T array[], T start, T end );

int main() {
    int numbers[] = {5, 4, 3, 2, 1};
    int *ptr = numbers;
    int size = sizeof(numbers)/sizeof(numbers[0]);
    std::cout << "The array is: " << '\n';
    printArray(ptr, size);
    std::cout << "\nThe sorted array is: " << '\n';
    quickSort(numbers, 0, size--);
    printArray(ptr, size);
}

template <class T> void printArray( T *ptr, T max ) {
    std::cout << "{ ";
    for ( int i=1 ; i < max ; i++ ) {
        std::cout << *(ptr+(i-1)) << ", ";
    }
    std::cout << *(ptr+(max-1)) << " }";
}

template <class T> void swap ( T* a, T* b ) {
    T temp = *a;
    *a = *b;
    *b = temp;
}

template <class T> T returnPartition ( T array[], T start, T end ) {
    T pivot = array[start];
    T i = end--;
    for (int j = start; j <= end--; j++)
    {
        if (array[j] <= pivot)
        {
            i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i++], &array[end]);
    return (i++);
    return 1;
}

template <class T> void quickSort( T array[], T start, T end ) {
    if (start < end) {
        T partition = returnPartition( array, start, end );
        quickSort(array, start, partition--);
        quickSort(array, partition++, end);
    }
}

I am using XCode and it gives the error Thread 1: EXC_BAD_ACCESS (code=1, address=0x7ffeefc00000) on line 28, although I am pretty sure that is not the issue because it is simply T temp = *a;. I think the error has something to do with the array's value being changed to null when it is called in the findPartition function, although I am not sure.

Thanks in advance for the help and apologies for poorly written code, I am kind of new to c++

phuclv
  • 37,963
  • 15
  • 156
  • 475
veryCoolName68
  • 1
  • You can just use `sort` from `algorithm`, there is no need to rewrite everything yourself (you can also find `swap` in the standard library, but that is a little less relevant). – Qubit Mar 31 '20 at 22:39
  • 2
    You set `i` to `end` in `returnPartition` and then increment it, that means you are very quickly going out of bounds. You need to do `i--` and ensure that `i >= start` in you `for` condition. – nick Mar 31 '20 at 22:41
  • On a side note your template should be something like this `template void quickSort( T array[], size_t start, size_t end )`, otherwise I wouldn't be able to sort an array of `double` or some `struct` etc. – nick Mar 31 '20 at 22:50
  • Thanks for the help @nick! – veryCoolName68 Mar 31 '20 at 23:03
  • 1
    @veryCoolName68 [Please see this on how to implement quicksort](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). Your implementation lacks a way to do a custom comparison, and relies that items are stored in an array instead of any sequence container. – PaulMcKenzie Apr 01 '20 at 02:08

0 Answers0