Document Status: In Progress

This guide is intended to cover a summary of major sorting algorithms along with the use case and relevant details.

1. Selection Sort
2. Insertion Sort
3. Shell Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort
7. Cyclic Sort
8. Bucket Sort
9. Radix Sort

1. Selection Sort

Algorithm

• Select an element , compare it with rest of the elements.
• Once minimum element found, swap it
• The elements to the left will always be sorted

Psuedo Code

	n -> array length
	for(i = 0; i < n - 1; i++)
		min = arr[i];
		for(int j = i + 1 ; j < n ; j++)
			if( arr[j] < min)
				min_index = j
				min = arr[j]
		//Swap the element with min index
		swap(arr, i, min_index)
				

Example

Compares

In selection sort, every element is compared with all the elements. It taks around T(~n ²/2) exchanges

Swaps/Exchange

In worst case, there would be T(n) swaps

Cons

• For sorted array, Selection sort takes O(n²)
• Input length doesnt affect the running time of the algorithm

Properties

• Minimum data movement

LC Questions

TBD

2. Insertion Sort

Algorithm

• Take an element, and keep on insert it into its proper place in already sorted array
• The elements to the left will always be sorted

Pseudocode

	for(int i = 0; i < n; i++)
		for(int j = i; j >0 && arr[j] < arr[j-1];j--)
			swap(arr, j, j-1)
			

Example

Compares

Average: It taks around T(~n ²/4) compares
Best: N - 1 Comares
Worst:T(~n ²/2)

Swaps/Exchange

In average case, there would be T(~n ²/4) swaps
In worst case, there would be T(~n ²/2) swaps
In best case, there would be 0 swaps

Property

• No swaps when array is already sorted
• Works best for partially sorted array

LC

• 147. Insertion Sort List

3. Shell Sort

Algorithm

• It is improvement on Insertion Sort
• We divide the array into mini arrays for kind of apply insertion sort on smaller arrays

TBD...
Resources:

• Algorithms - Fourth Edition , By Sedwig