Basic Sorting Algorithms in java

Here we implement bubble sort, selection sort, insertion Sort search algorithms and a brief introduction on Shell Sort.

In-place algorithms and stable algorithms

In-place means that the extra memory we need does not depend on the number of array elements to be sorted.
Stable means that if duplicate element exists, it will keep their original order after sorting.

Bubble Sort

First we devide the array logically into two partitions: Sorted partition and unsorted partition. We move larger elements into the right in each iteration.

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        arr = sort(arr);
        for (int i=0; i< arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static int[] sort(int[] arr) {
        for (int lastUnsortedPartitionIndex=arr.length-1; lastUnsortedPartitionIndex>0; lastUnsortedPartitionIndex--) {
            for (int j = 0; j < lastUnsortedPartitionIndex; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
}

• This is in-place algorithm.
• Time complexity is quadratic - O(n^2)
• Stable sort.

Selection Sort

First we devide the array logically into two partitions: Sorted partition and unsorted partition. Each iteration we select the largest element index, and swap it with the last unsorted partition index.

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        arr = sort(arr);
        for (int i=0; i< arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static int[] sort(int[] arr) {
        for(int lastUnsortedPartitionIndex = arr.length -1; lastUnsortedPartitionIndex > 0; lastUnsortedPartitionIndex--) {
            int largestIndex = 0;
            for (int i = 1; i <= lastUnsortedPartitionIndex; i++) {
                if (arr[largestIndex] < arr[i]) {
                    largestIndex = i;
                }
            }
            //swap
            int temp = arr[largestIndex];
            arr[largestIndex] = arr[lastUnsortedPartitionIndex];
            arr[lastUnsortedPartitionIndex] = temp;
        }
        return arr;
    }
}

• In-place algorithm
• Time complexity is quadratic - O(n^2)
• Does not require as much swapping as bubble sort
• Unstable algorithm

Insertion Sort

Here also, first we devide the array logically into two partitions: Sorted partition and unsorted partition.

• Assume index 0 is the sorted array partition initially.
• Then the first unsorted index becomes 1 from the unsorted partition.
• Now on each iteration, we take the first element from the unsorted partition (firstUnsortedIndex) and we insert it into the sorted partition.
• So at the end of each iteration, we have grown up the sorted array partition by one.

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        arr = sort(arr);
        for (int i=0; i< arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static int[] sort(int[] arr) {
        for (int firstUnsortedIndex=1; firstUnsortedIndex< arr.length; firstUnsortedIndex++) {
            // no need swapping
            // find the index and add new element to that index directly
            // initially index 0 is considered as the sorted array partition
            // we grow that sorted partition one by one
            int newElement = arr[firstUnsortedIndex];
            int index;
            for (index=firstUnsortedIndex; index>0 && arr[index-1] > newElement ; index--) {
                // shifting sorted partition elements until we find correct position to insert new element
                arr[index] = arr[index-1];
            }

            arr[index] = newElement; // insert new element
        }

        return arr;
    }
}

• In-place algorithm
• Time complexity is quadratic - O(n^2)
• No swapping
• Stable algorithm

Shell Sort

• A variation of insertion sort.
• In-place algorithm
• Introduce gap value
• Doesn't require as much shifting as insertion sort, so it usually performs better than insertion sort
• Unstable sort