Sorting

Bubble sort

Bubble sort is a simple sorting algorithm that compares adjacent elements of an array and swaps them if the element on the right is smaller than the one on the left. It is an in-place sorting algorithm i.e. no extra space is needed for this sort, the array itself is modified.

Code

private void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

Optimised Bubble sort

Same as a bubble sort, but if the input array is already sorted, sorting breaks after the first iterration

Code

private void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                swapped = true;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

Quick sort

Quicksort is a sorting algorithm belonging to the divide-and-conquer group of algorithms, and it's an in-place (no need for auxillary data structures), non-stable (doesn't guarantee relative order of same-value elements after sorting) sorting algorithm.

The divide-and-conquer algorithms recursively break down a problem into two or more sub-problems of the same type, making them simpler to solve. The breakdown continues until a problem is simple enough to be solved on it's own (we call this the base case).

In every step of the way an element is placed on the spot it belongs on in the sorted array.

This element is called the pivot. However, if we wanted to use the divide-and-conquer approach and reduce the problem of sorting the array to a smaller group of two sub-arrays we need to abide by the following: while we're placing our pivot at it's spot in the array we need to group the rest of the elements in two smaller groups - the ones left of the pivot are lesser or equal to it, and the ones on the right are bigger than the pivot.

This is actually the key step of the algorithm - called partitioning, and implementing it efficiently is a must if we want our Quicksort to be efficient as well.

Before discussing how Quicksort works, we should address how we choose which element is the pivot. The perfect scenario is that we always choose the element that splits the array in exact halves. However, since this is almost impossible to achieve, we can approach this problem in a few different ways.

For example, the pivot can be the first or the last element in the array (or a sub-array) we're currently processing. We can pick a median element as the pivot, or even choose a random element to play the role.
We have a variety of ways of accomplishing this task, and the approach we'll be taking in this article is to always choose the first (that is, left-most element of the array) as the pivot. Now let's jump into an example and explain how it all works.

Code

private void sort(int[] a, int low, int high) {
    if (low < high) {
        int q = partition(a, low, high);
        sort(a, low, q - 1);
        sort(a, q, high);
    }

}

private int partition(int[] a, int low, int high) {
    int q = low;
    for (int i = low; i < high; i++) {
        if (a[i] <= a[high]) {
            swap(a, i, q++);
        }
    }
    swap(a, high, q);
    return q;
}

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

Insert sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Code

private void sort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {

            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}

Merge sort

The merge sort algorithm is based on the principle of divide and conquer algorithm where a problem is divided into multiple sub-problems. Each sub-problem is solved individually and finally, sub-problems are combined to form the final solutions.

• Split array into two parts until the part contains 1 item
• When reached the base merge two sorted parts
• Repeat recursively

Code

private void sort(int[] a) {
    mergeSort(a, 0, a.length - 1);
}

private void mergeSort(int[] a, int left, int right) {
    if ( left < right) {
        int m = (right + left) / 2;

        mergeSort(a, left, m);
        mergeSort(a, m + 1, right);
        merge(a, left, m, right);
    }
}

private void merge(int[] a, int left, int m, int right) {

    int nL = m - left + 1;
    int nR = right - m;

    int[] leftArr = new int[nL];

    for (int i = 0; i < nL; i++) {
        leftArr[i] = a[left + i];
    }

    int[] rightArr = new int[nR];

    for (int j = 0; j < nR; j++) {
        rightArr[j] = a[m + 1 + j];
    }

    int i = 0;
    int j = 0;
    int c = left;
    while (i < nL && j < nR) {
        if (leftArr[i] <= rightArr[j]) {
            a[c++] = leftArr[i++];
        } else {
            a[c++] = rightArr[j++];
        }
    }
    while (i < nL) {
        a[c++] = leftArr[i++];
    }
    while (j < nR) {
        a[c++] = rightArr[j++];
    }
}

Comparison

Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Even a perfectly sorted input requires scanning the entire array
Insertion Sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	In the best case (already sorted), every insert requires constant time
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constant	Instable	By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depends	Stable	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.