Recent Posts

Quick Sort

Written by

Sonal Moga

Quick Sort

It is one of the fastest “in-place” sorting algorithms. In practice, quicksort is an O(n Log n) algorithm.

Quicksort begins by picking an element to be the pivot value. Pivot value can be any item from the array. The array is divided into three parts, the pivot value, one with values less than the selected pivot value and the third part having values greater than the pivot value item.

This process repeats itself till the array gets sorted, and in every turn, at least one element finds its final position and the partitions gets smaller. Eventually, partition is of size 1 and recursion ends.

Code:

//program to show quick sort

#include <iostream>
using namespace std;

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

int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void sortArray(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivot = partition(arr, low, high);
        sortArray(arr, low, pivot - 1);
        sortArray(arr, pivot + 1, high);
    }
}

void showArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        cout << arr[i] << "\t";
}

int main()
{
    int arr[] = { 6, 2, 8, 7, 3, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Input the elements of array" << endl;
    showArray(arr, n);
    cout << endl;
    sortArray(arr, 0, n-1); 
    cout<<"sorted array:"<<endl; 
    showArray(arr,n); 
    return 0; 
}

Output

Input the elements of array
6   2   8   7   3   9
sorted array:
2   3   6   7   8   9
Quick Sort