Insertion Sort

Insertion sort is a comparison sort algorithm with worst case complexity of O(n^2).

Insertion can be compared with the way cards are sorted manually in hand.

We first pick a card in hand. The 2nd card is picked and compared with first, if it is smaller it is placed ahead of it. The 3rd card is picked and compared with remaining cards in hand to find its final position.

At a time all the cards in hand are sorted and a new card is picked and “inserted” in its final position.

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

Complexity:

Worst case is when input is reverse sorted

T(n) = Total work done in each iteration.
In first iteration there is only one comparison
In second iteration there are two comparisons
and so on and so forth.
T(n) = 1 + 2 + 3 + … n = n^2 (arithmetic series)

Best case is already sorted array where complexity is O(n)

Git:
algorithms/src/main/java/org/nmn/notes/algorithms/sorting/InsertionSort.java

Bubble Sort

Bubble sort is a comparison sort algorithm where each pair of adjacent items are compared and swapping them if they are in wrong order to sort the array.

At the end of each iteration the largest element of that iteration will reach its final position.

For ex in array: [9, 3, 7, 8, 1]

At the end of 1st iteration, the 1st largest element 9 will reach its final position which is end of the array : [x, x, x, x, 9]
At the end of 2nd iteration, the 2nd largest element 8 will reach its final position which is 2nd last element in the array : [x, x, x, 8, 9]
So on and so forth, at the end of all iterations the array is going to be sorted.

Algorithm logic:

Total number of iterations = Total number of elements in the array, since at the end of one iteration, we will find largest element of that iteration only.

In each iteration:

  1. Start from index 0, compare adjacent elements, if left is greater than right, swap.
  2. Move right, compare again.

Lets sort array: [9, 3, 7, 8, 1]

Iteration 1:
[9, 3, 7, 8, 1]: 9 is greater than 3, swap elements:  [3, 9, 7, 8, 1]
[3, 9, 7, 8, 1]: 9 is greater than 7, swap elements:  [3, 7, 9, 8, 1]
[3, 7, 9, 8, 1]: 9 is greater than 8, swap elements:  [3, 7, 8, 9, 1]
[3, 7, 8, 9, 1]: 9 is greater than 1, swap elements: [3, 7, 8, 1, 9]
At the end of iteration 1, 9 has reached at the end of array.
Array at end of iteration: [3, 7, 8, 1, 9]

Iteration 2:
[3, 7, 8, 1, 9]
[3, 7, 8, 1, 9] ->  [3, 7, 1, 8, 9]
[3, 7, 1, 8, 9]
[3, 7, 1, 8, 9]
Array at end of 2nd iteration: [3, 7, 1, 8, 9]

Iteration 3:
[3, 7, 1, 8, 9]
[3, 7, 1, 8, 9] ->  [3, 1, 7, 8, 9]
[3, 1, 7, 8, 9]
[3, 1, 7, 8, 9]
Array at end of 3rd iteration: [3, 1, 7, 8, 9]

Iteration 4:
[3, 1, 7, 8, 9] -> [1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
Array at end of 4th iteration: [1, 3, 7, 8, 9]

Iteration 5:
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
Array at end of 4th iteration: [1, 3, 7, 8, 9]

Complexity:

Bubble sort algorithm is a comparison sort algorithm since we compare two elements to take a decision, any comparison sort algorithm cannot have complexity better than nlogn.

Lets find out complexity of bubble sort.
Complexity = (Total number of iterations) * (Work done in each iteration)

Total number of iterations = Total number of elements in an array = n.

Work done in each iteration = We start from index 0, compare adjacent elements and move right till the end of array, so in each iteration we do n-1 comparisons.

Complexity = n * (n-1) = n^2 – n = n^2 (ignore lower terms while computing complexity)

Worst-case T(n) = O(n^2)
Best-case T(n) = O(n)
Avg case T(n) = O(n^2)

Applications:

Bubble sort can be used to find ith largest element in the array. For ex, if you want to find 3rd largest element of the array, at the end of 3rd iteration the 3rd largest element will reach its final position which is 3rd last element from last.

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1)
            }
        }
    }

Bubble sort can be improved further by reducing the inner index since the largest element has already reached at the end.

Also, a swapped variable which is set to false at the start of the iteration and set to true only if elements are swapped. At the end of the iteration if swapped is still false, it means the array is sorted and does not require further comparisons. Hence, the best case for already sorted array is O(n).

Bubble sort does not require extra space to do the sorting, just one variable to do the swap which can also be avoided.

Bubble requires twice as many writes as insertion sort, 5 times slower than insertion sort and 40 times slower than selection sort.

Git:
algorithms/src/main/java/org/nmn/notes/algorithms/sorting/BubbleSort.java