Quick Sort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays, the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. (Wikipedia)

Worst case performance - O(n^2)

Source - Wikipedia

 C++

void quick_sort(int array[], int low, int high)
{
    if (low < high)
    {
        int q = partition(array, low, high);
        quick_sort(array, low, q - 1);
        quick_sort(array, q + 1, high);
    }
}

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

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Java

public void quick_sort(int[] array, int low, int high) {
    if (low < high) {
        int q = partition(array, low, high);
        quick_sort(array, low, q - 1);
        quick_sort(array, q + 1, high);
    }
}

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

public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Matlab

function array = quick_sort(array,low,high)
    if(low < high)
        [array,q] = partition(array, low, high);
        array = quick_sort(array, low, q - 1);
        array = quick_sort(array, q + 1, high);
    end
end

function [array,q] = partition(array,low,high)
    pivot = array(high);
    i = low - 1;
    for j= low : high - 1
        if (array(j) <= pivot)
            i = i + 1;
            array([j i]) = array([i j]);
        end
    end
    array([high i+1]) = array([i+1 high]);
    q = i + 1;
end

Python

def partition(array,low,high):
    pivot = array[high]
    i = low - 1
    for j in range(low,high):
        if array[j] <= pivot:
            i = i + 1
            array[i],array[j] = array[j],array[i]
    array[i+1],array[high] = array[high],array[i+1]
    return i+1

def quick_sort(array,low,high):
    if low < high:
        q = partition(array,low,high)
        quick_sort(array,low,q - 1)
        quick_sort(array,q + 1,high)