Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. (Wikipedia)

Worst case performance - O(n^2)

Bucket Sort

C++

void bucket_sort(int array[], int length)
{
    int k = max_value(array,length);
    int bucket[k+1];
    for(int i=0; i<=k; i++)
    {
        bucket[i] = 0;
    }
    for(int j=0; j<length; j++)
    {
        bucket[array[j]]++;
    }
    int index = 0;
    for (int i=0; i<=k; i++)
    {
        for (int j=0; j<bucket[i]; j++)
        {
            array[index++]=i;
        }
    }
}

int max_value(int array[], int length)
{
    int max = 0;
    for (int i = 0; i < length; i++)
        if (max < array[i])
            max = array[i];
    return max;
}

Java

public int[] bucket_sort(int[] array) {
    int k = max_value(array);
    int[] bucket = new int[k+1];
    for (int j = 0; j < array.length; j++) {
        bucket[array[j]]++;
    }
    int index = 0;
    for (int i = 0; i < bucket.length; i++) {
        for (int j = 0; j < bucket[i]; j++) {
            array[index++] = i;
        }
    }
    return array;
}

public int max_value(int[] array) {
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

Matlab

function array = bucket_sort(array)
    k = max(array);
    bucket = zeros(1,k+1);
    B = zeros(1,numel(array));
    for j = 1:numel(array)
        bucket(array(j)) = bucket(array(j)) + 1;
    end
    index = 1;
    for i = 1:k+1
        for j = 1:bucket(i)
            array(index) = i;
            index = index + 1;
        end
    end
end

Python

def bucket_sort(array):
    k = max(array)
    bucket = [0]* (k+1)
    for j in range(len(array)):
        bucket[array[j]] = bucket[array[j]] + 1
    index = 0
    for i in range(k+1):
        for j in range(bucket[i]):
            array[index] = i
            index = index + 1

Shell Sort

Shell sort is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). Shell sort starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. (Wikipedia)

Worst case performance - O(n^2)

Shell sort

C++

void shell_sort(int array[], int length)
{
    for (int gap = length/2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < length; i += 1)
        {
            int temp = array[i];
            int j;
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap)
                array[j] = array[j - gap];
            array[j] = temp;
        }
    }
}

Java

     public int[] shell_sort(int[] array) {
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i += 1) {
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }
                array[j] = temp;
            }
        }
        return array;
    } 

Matlab

function array = shell_sort(array)
    length = numel(array);
    gap = floor(length/2);
    while gap > 0
        for i = gap+1:length
            temp = array(i);
            j = i;
            while (j >= gap+1) && (array(j-gap) > temp)
                array(j) = array(j-gap);
                j = j - gap;
            end
            array(j) = temp;
        end
        gap = floor(gap/2);
    end
end

Python

import math

def shell_sort(array):
    length = len(array)
    gap = math.floor(length/2)
    while gap > 0:
        for i in range(gap,length):
            temp = array[i]
            j = i
            while (j >= gap) and (array[j - gap] > temp):
                array[j] = array[j-gap]
                j = j - gap
            array[j] = temp
        gap = math.floor(gap/2) 

Comb Sort

Comb sort is a comparison sorting algorithm improves on Bubble sort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Wikipedia)

Comb Sort

Worst case performance - O(n^2)

C++

void comb_sort(int array[], int length)
{
    int gap = length;
    bool swapped = true;
    while((gap > 1) || (swapped == true))
    {
        gap /= 1.25;
        if (gap < 1)
        {
            gap = 1;
        }
        int i = 0;
        swapped = false;
        while (i + gap < length)
        {
            if (array[i] > array[i + gap])
            {
                int temp = array[i];
                array[i] = array[i + gap];
                array[i + gap] = temp;
                swapped = true;
            }
            i++;
        }
    }
} 

Java

      public int[] comb_sort(int[] array) {
        int gap = array.length;
        boolean swapped = true;
        while ((gap > 1) || (swapped == true)) {
            gap /= 1.25;
            if (gap < 1) {
                gap = 1;
            }
            int i = 0;
            swapped = false;
            while (i + gap < array.length) {
                if (array[i] > array[i + gap]) {
                    int temp = array[i];
                    array[i] = array[i + gap];
                    array[i + gap] = temp;
                    swapped = true;
                }
                i++;
            }
        }
        return array;
    }

Matlab

function array = comb_sort(array)
    gap = numel(array);
    swapped = true;
    while (gap > 1) || swapped
        gap = floor(gap/1.25);
        if gap < 1
            gap = 1;
        end
        i = 1;
        swapped = false;
        while (i+gap-1) < numel(array)
            if array(i) > array(i+gap)
                array([i i+gap]) = array([i+gap i]);
                swapped = true;
            end
            i = i + 1;
        end
    end
end

Python

import math

def comb_sort(array):
    gap = len(array)
    swapped = True
    while gap > 1 or swapped :
        gap = math.floor(gap/1.25)
        if gap < 1 :
            gap = 1
        i = 0
        swapped = False
        while (i+gap)< len(array):
            if array[i] > array[i + gap]:
                temp = array[i]
                array[i] = array[i + gap]
                array[i + gap] = temp
                swapped = True
            i = i + 1

Radix Sort

The idea of explained Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit.

Worst case performance - O(n.k/d)

Radix sort

 C++

void radix_sort(int array[], int length)
{
    int k = max_value(array,length);
    for (int base = 1; k/base > 0; base *= 10)
        counting_sort(array,length,base);
}

void counting_sort(int array[], int length, int base)
{
    int C[10] = {0};
    int B[length];
    for (int j = 0; j < length; j++)
        C[(array[j]/base)%10]++;
    for (int i = 1; i < 10; i++)
        C[i] = C[i] + C[i - 1];
    for (int j = length - 1; j >= 0; j--)
    {
        B[C[(array[j]/base)%10] - 1] = array[j];
        C[(array[j]/base)%10]--;
    }
    for (int i = 0; i < length; i++)
        array[i] = B[i];
}

int max_value(int array[], int length)
{
    int max = 0;
    for (int i = 0; i < length; i++)
        if (max < array[i])
            max = array[i];
    return max;
} 

Java

public int[] radix_sort(int[] array) {
    int k = max_value(array);
    for (int base = 1; k / base > 0; base *= 10) {
        array = counting_sort(array, base);
    }
    return array;
}
public int[] counting_sort(int[] array, int base) {
    int[] C = new int[10];
    int[] B = new int[array.length];
    for (int j = 0; j < array.length; j++) {
        C[(array[j]/base)%10]++;
    }
    for (int i = 1; i < 10; i++) {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = array.length - 1; j >= 0; j--) {
        B[C[(array[j]/base)%10] - 1] = array[j];
        C[(array[j]/base)%10]--;
    }
    return B;
}
public int max_value(int[] array) {
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
} 

Matlab

function array = radix_sort(array)
k = max(array);
base = 1;
while k/base > 0
    array = counting_sort(array,base);
    base = base * 10;
end

    function B = counting_sort(array,base)
        C = zeros(1,11);
        B = zeros(1,numel(array));
        for j = 1:numel(array)
            C(rem(floor(array(j)/base),10)+1) = C(rem(floor(array(j)/base),10)+1) + 1;
        end
        for i = 2:11
            C(i) = C(i) + C(i-1);
        end
        for j = numel(array):-1:1
            B(C(rem(floor(array(j)/base),10)+1)) = array(j);
            C(rem(floor(array(j)/base),10)+1) = C(rem(floor(array(j)/base),10)+1) - 1;
        end
    end
end 

Python

import math

def counting_sort(array,base):
    C = [0]* (10)
    B = [0]* (len(array))
    for j in range(len(array)):
        C[math.floor(array[j]/base)%10] = C[math.floor(array[j]/base)%10] + 1
    for i in range(1,10):
        C[i] = C[i] + C[i-1]
    for j in range(len(array)-1,-1,-1):
        B[C[math.floor(array[j]/base)%10] - 1] = array[j]
        C[math.floor(array[j]/base)%10] = C[math.floor(array[j]/base)%10] - 1
    for i in range(len(array)):
        array[i] = B[i]

def radix_sort(array):
    k = max(array)
    base = 1
    while(k/base > 0):
        counting_sort(array,base)
        base = base * 10 

Counting Sort

Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. (Introduction to Algorithms)

Worst case performance - O(n + k)

 

Counting sort

 C++

void counting_sort(int array[], int length)
{
    int k = max_value(array,length);
    int C[k+1];
    int B[length];
    memset(C, 0, sizeof(C));
    for (int j = 0; j < length; j++)
        C[array[j]]++;
    for (int i = 1; i <= k; i++)
        C[i] = C[i] + C[i - 1];
    for (int j = length - 1; j >= 0; j--)
    {
        B[C[array[j]] - 1] = array[j];
        C[array[j]]--;
    }
    print_array(B,length);
}

int max_value(int array[], int length)
{
    int max = 0;
    for (int i = 0; i < length; i++)
        if (max < array[i])
            max = array[i];
    return max;
}

void print_array(int array[], int length)
{
    for(int i=0; i<length; i++)
        cout <<array[i]<<" ";
    cout << endl;
}

 Java

public int[] counting_sort(int[] array) {
    int k = max_value(array);
    int[] C = new int[k + 1];
    int[] B = new int[array.length];
    for (int j = 0; j < array.length; j++) {
        C[array[j]]++;
    }
    for (int i = 1; i <= k; i++) {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = array.length - 1; j >= 0; j--) {
        B[C[array[j]] - 1] = array[j];
        C[array[j]]--;
    }
    return B;
}

public int max_value(int[] array) {
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

 Matlab

function B = counting_sort(array)
    k = max(array);
    C = zeros(1,k+1);
    B = zeros(1,numel(array));
    for j = 1:numel(array)
        C(array(j)) = C(array(j)) + 1;
    end
    for i = 2:k+1
        C(i) = C(i) + C(i-1);
    end
    for j = numel(array):-1:1
        B(C(array(j))) = array(j);
        C(array(j)) = C(array(j)) - 1;
    end
end

 Python

def counting_sort(array):
    k = max(array)
    C = [0]* (k+1)
    B = [0]* (len(array))
    for j in range(len(array)):
        C[array[j]] = C[array[j]] + 1
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    for j in range(len(array)-1,-1,-1):
        B[C[array[j]] - 1] = array[j]
        C[array[j]] = C[array[j]] - 1
    print(B)

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)

Merge Sort

The basic idea of the algorithm is to split the collection into smaller groups by halving it until the groups only have one element or no elements (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order (Rosetta code). Merge sort follows divide-and-conquer approach.

Worst case performance - O(n log n)

Source - Wikipedia

 C++

 void merge_sort(int array[], int low, int high)  
 {  
   if (low < high)  
   {  
     int middle = (low + high) / 2;  
     merge_sort(array,low, middle);  
     merge_sort(array,middle + 1, high);  
     merge(array, low, middle, high);  
   }  
 }  
   
 void merge(int array[], int low, int middle, int high)  
 {  
   int size1 = middle - low + 1;  
   int size2 = high - middle;  
   int left[size1 + 1];  
   int right[size2 + 1];  
   for (int i = 0; i < size1; i++)  
   {  
     left[i] = array[low + i];  
   }  
   for (int j = 0; j < size2; j++)  
   {  
     right[j] = array[middle + j + 1];  
   }  
   left[size1] = numeric_limits<int>::max();;  
   right[size2] = numeric_limits<int>::max();;  
   int i = 0;  
   int j = 0;  
   for (int k = low; k <= high; k++)  
   {  
     if (left[i] <= right[j])  
     {  
       array[k] = left[i];  
       i++;  
     }  
     else  
     {  
       array[k] = right[j];  
       j++;  
     }  
   }  
 }   

Java

   static int[] array = {5, 4, 8, 3, 1, 2, 9, 6, 7, 10};  
   
   static void merge_sort(int[] array, int low, int high) {  
       if (low < high) {  
         int middle = (low + high) / 2;  
         merge_sort(array, low, middle);  
         merge_sort(array, middle + 1, high);  
         merge(array, low, middle, high);  
       }  
    }  
   
   static void merge(int[] array, int low, int middle, int high) {  
       int size1 = middle - low + 1;  
       int size2 = high - middle;  
       int[] left = new int[size1 + 1];  
       int[] right = new int[size2 + 1];  
       for (int i = 0; i < size1; i++) {  
         left[i] = array[low + i];  
       }  
       for (int j = 0; j < size2; j++) {  
         right[j] = array[middle + j + 1];  
       }  
       left[size1] = Integer.MAX_VALUE;  
       right[size2] = Integer.MAX_VALUE;  
       int i = 0;  
       int j = 0;  
       for (int k = low; k <= high; k++) {  
         if (left[i] <= right[j]) {  
           array[k] = left[i];  
           i++;  
         } else {  
           array[k] = right[j];  
           j++;  
         }  
       }  
    }  

Matlab

   function array = merge_sort(array,low,high)  
     if(low < high)  
       middle = floor((low + high)/2);  
       array = merge_sort(array,low, middle);  
       array = merge_sort(array,middle + 1, high);  
       array = merge(array, low, middle, high);  
     end  
   end  
   
   function array = merge(array,low,middle,high)  
     size1 = middle - low + 1;  
     size2 = high - middle;  
     left = zeros(1,size1+1);  
     right = zeros(1,size2+1);  
     for i=1:size1  
       left(i) = array(low+i-1);  
     end  
     for j=1:size2  
       right(j) = array(middle+j);  
     end  
     left(size1+1) = inf;  
     right(size2+1) = inf;  
     i = 1;  
     j = 1;  
     for k=low:high  
       if left(i)<= right(j)  
         array(k) = left(i);  
         i = i + 1;  
       else  
         array(k) = right(j);  
         j = j + 1;  
       end  
     end  
   end   

Python 

import math

def merge(array,low,middle,high):
    size1 = middle - low + 1
    size2 = high - middle
    left = [0]* (size1+1)
    right = [0]* (size2+1)
    for i in range(size1):
        left[i] = array[low+i]
    for j in range(size2):
        right[j] = array[middle+j+1]
    left[size1] = float("inf")
    right[size2] = float("inf")
    i = 0
    j = 0
    for k in range(low,high+1):
        if left[i]<= right[j]:
            array[k] = left[i]
            i = i + 1
        else:
            array[k] = right[j]
            j = j + 1
   
def merge_sort(array,low,high):
    if low<high:
        middle = int(math.floor((low+high)/2))
        merge_sort(array,low,middle)
        merge_sort(array,middle+1,high)
        merge(array,low,middle,high)

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. (Wikipedia)

Worst case performance - O(n^2)

Source - Wikipedia

C++

void bubble_sort(int array[], int length)
{
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 1; i < length; i++)
        {
            if (array[i - 1] > array[i])
            {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
            }
        }

    }
    while (swapped);
}

Java

public int[] bubble_sort(int[] array) {
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
            }
        }

    } while (swapped);
    return array;
}

Matlab

function array = bubble_sort(array)
    length = numel(array);
    swapped = true;
    while swapped
        swapped = false;
        for i=2:length
            if array(i-1)>array(i)
                array([(i-1) i]) = array([i (i-1)]);
                swapped = true;
            end
        end
    end
end

Python

def bubble_sort(array):
  swapped = True
 
  while swapped:
    swapped = False
   
    for i in range(1,len(array)):
      if array[i-1]>array[i]:
        temp = array[i]
        array[i] = array[i - 1]
        array[i - 1] = temp
        swapped = True
      

More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. (Wikipedia). Therefore we can further optimize the algorithm. Here is the Java implementation of the optimized algorithm.

 public int[] bubble_sort(int[] array) {
    int n = array.length;
    int newLimit = 0;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (array[i - 1] > array[i]) {
                int temp = array[i];
                array[i] = array[i - 1];
                array[i - 1] = temp;
                swapped = true;
                newLimit = i;
            }
        }
        n = newLimit;

    } while (swapped);
    return array;
}

Selection Sort

The main idea of the algorithm is quite simple as follows. The input data array is divided to two imaginary parts, sorted and unsorted. Initially the sorted part is empty. The algorithm searches for the smallest element of the unsorted part and adds it to the end of the sorted part. When the unsorted part becomes empty algorithm stops. However Selection sort is inefficient in sorting large sets.

Worst case performance - O(n^2)

Source - Quazoo

C++

void selection_sort(int array[], int length)
{
    for (int j = 0; j < length - 1; j++)
    {
        int min = j;
        for (int i = j + 1; i < length; i++)
        {
            if (array[i] < array[min])
            {
                min = i;
            }
        }
        if (min != j)
        {
            int temp = array[j];
            array[j] = array[min];
            array[min] = temp;
        }
    }
}

 Java

public int[] selection_sort(int[] array) {
    for (int j = 0; j < array.length - 1; j++) {
        int min = j;
        for (int i = j + 1; i < array.length; i++) {
            if (array[i] < array[min]) {
                min = i;
            }
        }
        if (min != j) {
            int temp = array[j];
            array[j] = array[min];
            array[min] = temp;
        }
    }
    return array;
}

Matlab

function array = selection_sort(array)
    length = numel(array);
    for i = (1:length-1)
        min = i;
        for j = (i+1:length)
            if array(j) <= array(min)
                min = j;
            end
        end
        if i ~= min
            array([min i]) = array([i min]);
        end
    end
end

Python

def selection_sort(array):
  for j in range(len(array)-1):
 
    min = j
    
    for i in range(j+1,len(array)):
      if array[i] < array[min]:
        min = i
        
    if min != j:
      temp = array[j]
      array[j] = array[min]
      array[min] = temp

Insertion Sort

When we need to sort small number of elements, Insertion sort would be an efficient algorithm. Insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.(Wikipedia)

Worst case performance - O(n^2)

Source - Introduction to Algorithms 3e

C++

void insertion_sort(int array[], int length)
{
    for(int j=1; j<length; j++)
    {
        int key = array[j];
        int i = j-1;
        while(i>=0 && array[i]>key)
        {
            array[i+1] = array[i];
            i = i-1;
        }
        array[i+1] = key;
    }
}

Java

public int[] insertion_sort(int[] array) {
    for (int j = 1; j < array.length; j++) {
        int key = array[j];
        int i = j - 1;
        while (i >= 0 && array[i] > key) {
            array[i + 1] = array[i];
            i = i - 1;
        }
        array[i + 1] = key;
    }
    return array;
}

Matlab

function array = insertion_sort(array)
    for i = 2:numel(array)
        key = array(i);
        j = i - 1;
        while (j > 0) && (array(j) > key)
            array(j+1) = array(j);
            j = j-1;
        end
        array(j+1) = key;
    end
end

Python

def insertion_sort(array):
   for j in range(1,len(array)):

     key = array[j]
     i = j

     while i>0 and array[i-1]>key:
         array[i] = array[i-1]
         i = i-1

     array[i] = key

If we closely look at the Insertion sorting algorithm, we can see that still it is possible to increase the efficiency of the algorithm by doing some changes. Since the correct position of the inserting element is found from the already sorted part of the array, we can perform binary search algorithm to that part of the array. Here is the Python implementation of the modified algorithm.

def insertion_sort(array):
    for i in range(1, len(array)):
 
        key = array[i]
        low, high = 0, i
     
        while high > low:
            mid = (low + high) // 2
            if array[mid] < key:
                low = mid + 1           
            else:
                high = mid
             
     array[:] = array[:low] + [key] + array[low:i] + array[i+1:]

Sorting algorithms

The main purpose of a sorting algorithm is to arrange the elements of a list or an array in a certain order. In this post I am going to discuss 11 sorting algorithms described in Wikipedia.

1. Insertion sort
2. Selection sort
3. Merge sort
4. Heap sort
5. Quick sort
6. Bubble sort
7. Shell sort
8. Comb sort
9. Counting sort
10. Bucket sort
11. Radix sort