Different Sorting Algorithms

In this article, we will be discussing different sorting techniques and algorithms with examples that are most frequently used in computer science. We will discuss Bubble sort, Selection Sort, Insertion Sort, Merge Sort, and Quicksort along with their best and worst-case complexity. The example code will be in Java programming language.

What is Sorting

Sorting is an algorithm that arranges the elements of a collection in a particular order that may be in either ascending or descending order. A sorted collection significantly reduces the searching complexity of en elements in a collection. For example, a binary search is always performed on sorted elements which can then provide a worst-case complexity of O(log n).

Now, let us discuss each sorting techniques algorithm one by one.

Bubble Sort

Bubble sort is the simplest sorting algorithm. It sorts an input array by iterating the array from the first element to last, comparing each pair of elements and swapping them if needed. Hence, it can detect whether the input list is already sorted or not. This sorting technique continues its iterations until no more swaps are needed.

The algorithm gets its name from the way smaller elements bubble to the top of the list. Insertion sort is more preferred over Bubble sort for a better performance.

Below is the Java implementation of Bubble sort.

public void bubbleSort(int[] input){
        System.out.println("Input array " + Arrays.toString(input));
        for(int i = input.length - 1; i >= 0; i--){
            for(int j = 0; j <= i - 1; j++){
                if(input[j] > input[j + 1]){
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
        }
        System.out.println("Output Array: " + Arrays.toString(input));
    }

Bubble Sort Performance

Worst case complexity : O(n^2)

Best case complexity : O(n)

Average case complexity : O(n^2)

Worst case space complexity : O(1)

Selection Sort

Selection sort is an in-place sorting algorithm. This sorting algorithm selects the smallest element in the input array first and swaps it with the value in the current position. This process is repeated for all the remaining elements until the entire array is sorted.

This algorithm does not require any additional storage space and hence its an in-place sorting technique. Due to it's in-place sorting technique, this sorting technique can be used to perform the sorting of large files.

Below is the Java program that performs Selection sort on any given array.

public void selectionSort(int[] inputArray){
        System.out.println("Input array " + Arrays.toString(inputArray));
        for(int i = 0; i < inputArray.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < inputArray.length; j++){
                if(inputArray[j] < inputArray[min]){
                    min = j;
                }
                int temp = inputArray[min];
                inputArray[min] = inputArray[i];
                inputArray[i] = temp;
            }
        }
        System.out.println("Sorted array " + Arrays.toString(inputArray));
    }

Selection Sort Performance

Worst case Complexitiy : O(n^2)

Best case Complexity: O(n^2)

Average Case Complexity: O(n^2)

Worst case space Complexity: O(1)

Insertion Sort

In Insertion sort, each iteration removes an element from the input data and inserts it into the correct position in the list being sorted. The choice of the element being removed from the input is random and this process is repeated until all input elements have gone through. It requires only a constant amount O(1) of additional memory space.

Insertion sort as per the name directly inserts an element at it's correct position.

public void insertionSort(int[] inputArray){
        System.out.println("Input array " + Arrays.toString(inputArray));
        for(int i = 0; i < inputArray.length; i++ ){
            int temp = inputArray[i];
            int j = i;
            while(j > 0 && inputArray[j -1] > temp){
                inputArray[j] = inputArray[j - 1];
                j = j - 1;
            }
            inputArray[j] = temp;
        }
        System.out.println("Sorted array " + Arrays.toString(inputArray));
    }

Insertion Sort Performance

Worst case Complexitiy : O(n^2)

Best case Complexity: O(n^2)

Average Case Complexity: O(n^2)

Worst case space Complexity: O(n^2) total

Comparison of Bubble Sort, Insertion Sort and Selection Sort

Though the time complexity of all these algorithms is O(n^2), there are some subtle differences between them and these differences can help us to choose the right sorting algorithm for different use cases.

Quick Sort

Quick sort, also known as partition excahnge sort, is an a divide-and-conquer algorithmic technique. It uses recursive calls for sorting the elements. For quick sort, pick any element in the array as a pivot element and split the array into 2 parts - one with elements larger than the pivot and the other with elements smaller than the pivot. Then, recursively repeat the algorithm for both halves of the original array.

Below is the Java program for quick sort.

public class QuickSort {

    public void quickSort(int[] input, int low, int high){

        if(high > low){
            int pivot = partition(input, low, high);
            quickSort(input, low, pivot - 1);
            quickSort(input, pivot + 1, high);
        }
    }

    private int partition(int[] array, int low, int high){
        int left, right, pivot_item = array[low];
        left = low;
        right = high;
        while(left < right){
            while(array[left] <= pivot_item)
                left++;
            while (array[right] > pivot_item)
                right--;
            if(left < right){
                swap(array, left, right);
            }
        }
        array[low] = array[right];
        array[right] = pivot_item;
        return right;
    }

    private void swap(int[] array, int left, int right){
        int temp;
        temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args){
        QuickSort quickSort = new QuickSort();
        int[] array = {8, 5, 3, 9, 1, 4, 12};
        System.out.println("Input array " + Arrays.toString(array));
        quickSort.quickSort(array, 0, array.length - 1);
        System.out.println("Sorted array " + Arrays.toString(array));
    }
}

Quick Sort Complexity

Worst case Complexitiy : O(n^2)

Best case Complexity: O(nlogn)

Average Case Complexity: O(nlogn)

Worst case space Complexity: O(1)

Merge Sort

Merge sort is an example of a divide and conquer algorithm. In Merge sort, the input list is divided into two parts recursively to convert the input list into sub list of single element and then these sub-lists are merged into a sorted list. This sorting technique is very stable and provides a worst-case complexity of nlogn. Java internally uses Merge sort to sort the collections.

Below is the Java program for merge sort.

public void mergeSort(int input[], int left, int right){
        if (left < right) {
            int mid = (left + right)/2;
            mergeSort(input, left, mid);
            mergeSort(input , mid + 1, right);
            merge(input, left, mid, right);
        }
    }

Merge Sort Complexity

Worst case Complexitiy : O(nlogn)

Best case Complexity: O(nlogn)

Average Case Complexity: O(nlogn)

Worst case space Complexity: O(n) total

Why Mergesort is preferred over Quicksort for Linked Lists

Quick Sort is an in-place sort (i.e. it doesn’t require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm.

Mergesort is always preferred over Quicksort for Linked Lists mainly because of the memory allocations. Memory allocations in an Array are contiguous whereas linked list nodes may not be adjacent in memory. Due to this contiguous memory allocation in an Array, we can randomly access any array elements with the time complexity of O(1). Suppose, we have an integer(4 byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at [x + (i * 4)] and Quicksort requires a lot of this kind of access.

Hence, we generally prefer Quicksort for sorting an Array. But in a linked list the worst-caase time complexity to access an element is O(n). Hence, merge sort is more preferred to sort a linked list.

In most of the cases, arrays are smaller in size. Hence, we can go with it's best case time complexity of O(nlogn)

Stable and Unstable Sorts

Let us assume we have an array to sort and this array contains duplicate elements. If the order of occurrence of these duplicate elements is maintained after the sorting algorithm is applied, then this sorting algorithm is assumed to be stable.

In the below sorting technique image, 8 is a duplicate element. The stable sort maintains the order of occurrence whereas unstable sort does not maintain the order of occurrence.

If you see the while condition in the insertion sort technique implemented above, we are using a strict check as inputArray[j -1] > temp for the stability of the algorithm.

while(j > 0 && inputArray[j -1] > temp){
      inputArray[j] = inputArray[j - 1];
      j = j - 1;
}

Conclusion

In this article, we discussed about some of the most used sorting algorithm along with thier implementation in Java and thier complexity.