C++ quick sort algorithm

Question

I'm not looking to copy a qsort algorithm. I'm practicing writing qsort and this is what I've come up with and I'm interested in what part of my code is wrong. Please don't tell me that this is homework cause I could just use the code in the link below.

Reference: http://xoax.net/comp/sci/algorithms/Lesson4.php

When this runs I get this in the console:

Program loaded.
run
[Switching to process 10738]
Running…
Current language:  auto; currently c++
Program received signal:  “EXC_ARITHMETIC”.


void myQSort(int min, int max, int* myArray)
    {
        // Initially find a random pivot
        int pivotIndex = rand() % max;
            int pivot = myArray[pivotIndex];

        int i = 0 , j = max-1;

        // Pointer to begining of array and one to the end

        int* begin = myArray;
        int* end = &myArray[max-1];

        // While begin < end 
        while( begin < end )
        {
        // Find the lowest bound number to swap
            while( *begin < pivot )
            {
                begin++;
            }
            while( *end > pivot ) 
            {
                // Find the highest bound number to swap
                end--;
            }

        // Do the swap
            swap(begin,end);
        }
        // Partition left
        myQSort(0, pivotIndex-1, myArray);
        // Partiion right
        myQSort(pivotIndex+1,max, myArray);

    }

EDIT-- Code for Swap:

void swap(int* num, int* num2)
{
    int temp = *num;
    *num = *num2;
    *num2 = temp;
}

Answer 1

// sort interval [begin, end)
void myQSort(int* begin, int* end)
{
    if(end - begin < 2)
        return;
    int* l = begin;
    int* r = end - 1;

    // Initially find a random pivot
    int* pivot = l + rand() % (r - l + 1);
    while(l != r)
    {
        // Find the lowest bound number to swap
        while(*l < *pivot) ++l;
        while(*r >= *pivot && l < r) --r;

        // Do the swap
        if(pivot == l) { pivot = r; }
        std::swap(*l, *r);
    }

    // Here l == r and numbers in the interval [begin, r) are lower and in the interval [l, end) are greater or equal than the pivot
    // Move pivot to the position
    std::swap(*pivot, *l);

    // Sort left
    myQSort(begin, l);
    // Sort right
    myQSort(l + 1, end);
}

Answer 2

I tried working out the codes above. But, they don't compile.

@Mihran: Your solution is correct algorithmically but the following line generates an error:

myQSort(min, begin - myArray, myArray);

This is because begin is of type int* and myArray is of type long, following which the compiler shows this error message:

implicit conversion loses integer precision

Here's a working solution in C++:

#include <iostream>
using namespace std;

void mySwap(int& num1, int& num2){
    int temp = num1;
    num1 = num2;
    num2 = temp;
}

void myQsort(int myArray[], int min, int max){
    int pivot = myArray[(min + max) / 2];

    int left = min, right = max;

    while (left < right) {
        while (myArray[left] < pivot) {
            left++;
        }
        while (myArray[right] > pivot) {
            right--;
        }

        if (left <= right) {
            mySwap(myArray[left], myArray[right]);
            left++;
            right--;
        }
    }

    if (min < right) {
        myQsort(myArray, min, right);
    }
    if (left < max) {
        myQsort(myArray, left, max);
    }
}

int main()
{
    int myArray[] = {1, 12, -5, 260, 7, 14, 3, 7, 2};
    int min = 0;
    int max = sizeof(myArray) / sizeof(int);

    myQsort(myArray, min, max-1);

    for (int i = 0; i < max; i++) {
        cout<<myArray[i]<<" ";
    }

    return 0;
}

Answer 3

Here's a clear C++ implementation, for reference:

#include <iostream>
#include <vector>

using namespace std;

int partition(std::vector<int>& arr, int low, int high) {
    // set wall index
    int wall_index = low;
    int curr_index = low;
    int pivot_elem = arr[high]; // taking last element as pivot_element

    // loop through the entire received arr
    for (int i = curr_index; i < high; ++i) {
        // if element is less than or equal to pivot_elem
        // swap the element with element on the right of the wall
        // i.e swap arr[i] with arr[wall_index]
        if (arr[i] <= pivot_elem) {
            // swap
            int temp = arr[wall_index];
            arr[wall_index] = arr[i];
            arr[i] = temp;

            // move the wall one index to the right
            wall_index++;
            curr_index++;
        } else {
            // if the element is greater than the pivot_element
            // then keep the wall at the same point and do nothing
            curr_index++;
        }
    }

    // need to swap the pivot_elem i.e arr[high] with the element right of the wall
    int temp = arr[wall_index];
    arr[wall_index] = arr[high];
    arr[high] = temp;

    return wall_index;
}

void quick_sort(std::vector<int>& arr, int low, int high) {
    if (low < high) { // element with single arr always have low >= high
        int split = partition(arr, low, high);

        quick_sort(arr, low, split-1);
        quick_sort(arr, split, high);
    }
}

int main() {
    std::vector<int> data = {6,13,8,4,2,7,16,3,8};
    int N = data.size();
    quick_sort(data, 0, N-1);

    for (int i : data) {
        cout << i << " ";
    }

    return 0;
}

Answer 4

You're not using the min parameter in your code, anywhere. You need to set begin and your pivot value using that.

Answer 5

I don't see a clean implementation of Quicksort on SO, so here is my easy to understand implementation

PLEASE DONT USE IN PRODUCTION CODE

This is only for your understanding

// Swap position a with b in an array of integer numbers
void swap(int *numbers, int a, int b){
   int temp = numbers[a];
   numbers[a] = numbers[b];
   numbers[b] = temp;
} 

static int partition(int *data, int low, int high) {

    int left = low,  right = high,  pivot = data[low];

    while (left < right) {

        // Everthing on the left of pivot is lower than the pivot 
        while ((left <= right) && data[left] <= pivot) // <= is because left is the pivot initially
            left++;

        // Everything on the right of the pivot is greater than the pivot 
        while((left <= right) && data[right] > pivot)
            right--;

        if (left < right)
            swap(data, left, right);
    }

    // Put the pivot in the 'rigthful' place
    swap(data, low, right);

    return right;
}

// Quicksort 
static void quick_sort(int *numbers, int low, int high)
{
    if (high > low) {
        int p_index = partition(numbers, low, high);

        quick_sort(numbers, low , p_index - 1);
        quick_sort(numbers, p_index + 1, high);
    }
}