Insertion Sort

Data structure: Array

Worst case performance: O(n^{2}) comparisons, swaps

Best case performance: O(n) comparisons, O(1) swaps

Average case performance: O(n^{2}) comparisons, swaps


Insertion sort iterates through the list by consuming one input element at each repetition, and growing a sorted output list. On a repetition, 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.

Algorithm:

//insertion sort algo where we keep comparing the current element arr[i] with elements from indexes 

//(i to 0) and keep shifting elements to the right to free a space for arr[i]

insertionSort(arr)

for every element i in arr{

currentElement = arr[i]

j = i - 1;

while(j > 0){

if(currentElement < arr[j]){

// shift elements to right

arr[j+1] = arr[j]

}

j--;

}

swap(arr[i], arr[j])

}

Example:
The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}. In each step, the key under consideration is underlined. The key that was moved (or left in place because it was biggest yet considered) in the previous step is shown in bold.

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array. Insertion sort's advantage is that it only scans as many elements as needed to determine the correct location of the k+1st element, while selection sort must scan all remaining elements to find the absolute smallest element.

http://www.java2novice.com/java-sorting-algorithms/insertion-sort/

https://en.wikipedia.org/wiki/Insertion_sort

Selection Sort

Data structure: Array

Worst case performance: O(n^{2})

Best case performance: O(n^{2})

Average case performance: O(n^{2})


Example:

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists,

For a list with n elements the number of passes required to sort will be n-1 with the smallest element placed in the leftmost position (for ascending order sort) in the first pass. Therefore, for a list with k sorted elements, passes required will be n - k

// selecton sort algo for ascending order
selsort(arr)
for every element i in arr{
minIndex = i //assume starting with first element to be the minimum
for every i+1 element in arr{
if(arr[i] > arr[i+1]){
minIndex = i+1 //set next index as new min
}
}

if(i != minIndex){
swap(arr[i], arr[minIndex])
}

}


http://www.java2novice.com/java-sorting-algorithms/selection-sort/
https://en.wikipedia.org/wiki/Selection_sort
http://www.cs.armstrong.edu/liang/animation/web/SelectionSort.html

Bubble Sort

Data structure: Array

Worst case performance: O(n^{2})

Best case performance: O(n)

Average case performance: O(n^{2})




Example:

Array elements - 5 3 1 6 7 8 2 4


Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared. The largest element gets sorted to the end of the list first, with the smaller elements getting sorted with each iteration one by one.

Bubble sort is not a practical sorting algorithm when n is large.


https://en.wikipedia.org/wiki/Bubble_sort