Quick Sort

Quick sort is a divide and conquer based algorithm like merge sort. I provide my implementation of quick sort which is implemented recursively.

#include <iostream>
#include <cstring>

using namespace std;

void display(int* arr, size_t size)
{
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << endl;
    }
}

int partition(int pivot, int* arr, size_t size, int left, int right)
{
    int pivotIndex = left;
    left++;

    while (left < right) {
        while(pivot > arr[left] && left < size)
            left++;

        while(pivot < arr[right] && right > 0)
            right--;

        if (left >= right)
            break;

        swap(arr[left], arr[right]);
    }

    swap(arr[pivotIndex], arr[right]);

    return right;
}

void quick_sort(int* arr, size_t size, int left, int right)
{
    if (right-left <= 0)
        return;

    int pivot = arr[left];

    int newPivotIndex = partition(pivot, arr, size, left, right);

    quick_sort(arr, size, left, newPivotIndex-1);
    quick_sort(arr, size, newPivotIndex+1, right);
}

int main() {
    int A[] = {20,10,30,50,100,60,40,90,80,70};

    display(A, 10);

    cout << endl;

    quick_sort(A, 10, 0, 9);

    display(A, 10);

    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *