Heap Sort

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.(Wikipedia)

Worst case performance - O(n log n)

Heap sort

C++

void heap_sort(int array[],int heap_size){
    build_max_heap(array,heap_size);
    for (int i = heap_size; i > 0; i--) {
        swap(array,0, i);
        heap_size = heap_size - 1;
        max_heapify(array, 0,heap_size);
    }
}

void build_max_heap(int array[], int heap_size){
    for (int i = heap_size / 2; i >= 0; i--){
        max_heapify(array, i,heap_size);
    }
}

void max_heapify(int array[], int i,int heap_size){
    int l = left(i);
    int r = right(i);
    int largest;
    if (l <= heap_size && array[l] > array[i]){
        largest = l;
    }
    else{
        largest = i;
    }
    if (r <= heap_size && array[r] > array[largest]){
        largest = r;
    }
    if (largest != i){
        swap(array,i, largest);
        max_heapify(array, largest,heap_size);
    }
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return 2 * i + 1;
}

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

Java

    public void heap_sort(int[] array) {
        build_max_heap(array);
        for (int i = heap_size; i > 0; i--) {
            swap(0, i);
            heap_size = heap_size - 1;
            max_heapify(array, 0);
        }
    }
   
    public void build_max_heap(int[] array) {
        heap_size = array.length - 1;
        for (int i = heap_size / 2; i >= 0; i--) {
            max_heapify(array, i);
        }
    }
   
    public void max_heapify(int[] array, int i) {
        int l = left(i);
        int r = right(i);
        int largest;
        if (l <= heap_size && array[l] > array[i]) {
            largest = l;
        } else {
            largest = i;
        }
        if (r <= heap_size && array[r] > array[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(i, largest);
            max_heapify(array, largest);
        }
    }
   
    public int left(int i) {
        return 2 * i;
    }
   
    public int right(int i) {
        return 2 * i + 1;
    }
   
    public void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

Matlab

function array = heap_sort(array)
    heap_size = numel(array);
    array = build_max_heap(array,heap_size);
    for i = numel(array):-1:2
        array([i 1]) = array([1 i]);
        heap_size = heap_size - 1;
        array = max_heapify(array,heap_size,1);
    end
end

function array = build_max_heap(array,heap_size)
    for i = floor(heap_size/2):-1:1
        array = max_heapify(array,heap_size,i);
    end
end

function array = max_heapify(array,heap_size,i)
    l = left(i);
    r = right(i);
    if l <= heap_size && array(l) > array(i)
        largest = l;
    else
        largest = i;
    end
    if r <= heap_size && array(r) > array(largest)
        largest = r;
    end
    if largest ~= i
        array([largest i]) = array([i largest]);
        array = max_heapify(array,heap_size,largest);
    end
end

function l = left(i)
    l = 2 * i;
end

function r = right(i)
    r = 2 * i + 1;
end

Python

import math

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def max_heapify(array,heap_size,i):
    l = left(i)
    r = right(i)
    if l <= heap_size and array[l] > array[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size and array[r] > array[largest]:
        largest = r
    if largest != i:
        array[largest],array[i] = array[i],array[largest]
        max_heapify(array,heap_size,largest)

def build_max_heap(array,heap_size):
    for i in range(math.floor(heap_size/2),-1,-1):
        max_heapify(array,heap_size,i)

def heap_sort(array):
    heap_size = len(array)- 1
    build_max_heap(array,heap_size)
    for i in range(heap_size,0,-1):
        array[i],array[0] = array[0],array[i]
        heap_size = heap_size - 1
        max_heapify(array,heap_size,0)

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)