Algorithms and Data Structures : Sorting

1) Bubble Sort 

5,4,19,3,0,2,7

Theory : 1) Start from LHS and compare each number to its adjacent number.  Exchange
               the two numbers if LHS number is bigger than RHS.
             
               2) If N is number of value to be sorted, then doing  Step 1) for N times will sort the values.

Time Complexity : N^2.
Space Complexity : No additional space is required.

Easy to code and better approach when sorting N < 50.

Optimization : We can check if at same stage , the number of exchanges are zero we can stop at that point.

2) Counting Sort

5,4,19,3,0,2,7

Theory:  1) For each number store , how many times that number is coming in new array

count[0]=1;   count[7]=1;
count[1]=0;   count[8]  till count[18]  is 0;
count[2]=1;   count[19]=1;
count[3]=1;
count[4]=1;
count[5]=1;
count[6]=0;

now since we know, how many times a particular number is coming. We can now output sorted number based on count values.
0,2,3,4,5,7,19

Time complexity is 0(K)  where K is the largest number.
Space Complexity is 0(K) where K is largest number.

This approach can be used , when the diff between smallest and largest number is small.

Ex:  100,50,4,1

now to sort these 4 numbers : Bubble sort will have at max - 16 sec, if we assume 1 sec for each compare.
But Counting sort will take 100 sec, since we have to fill count array.

but for  10,6,4,1,2,8,9,5,3,7

bubble sort  100 sec.
count 10 sec.


But since in real life we seldom knows the input values, we take approach which doesn't fluctuates much.

3) Selection Sort

In this sort, select the biggest element / smallest element and place at the end/front.
Continue to this for N times and array will be sorted.

Time Complexity : O(N^2)
Space Complexity: None , no additional space needed.

It is never used, as it doesn't provide any improvement over bubble sort

4) Quick Sort

69 10 30 2 16 8 31 22

The strategy behind this is to divide select a pivot( one element). In logN time we can find pivot correct value.
Doing this for each N element we can place it in correct place.

Select one element ( we select the middle element of given numbers). Then check its LHS to number greater than this. If we find such number, stop at that.

Then at RHS of this element , find number smaller than this.  If such number exist, swap them.

Else we will continue to do this, untill we reach same number from both LHS and RHS.
The position of this number is the correct position of our PIVOT element.

We will exchange PIVOT number with this, after that , we will do same process for our left subset and right subset , w.r.t to out PIVOT ELEMENT.

Time Complexity : O(nlogn)
Space Complexity : Since we use recursion for this, lot of space will be used by system.

This can be used when there is less constraint on memory and more constraint on time.

But the process of merge sort can be used to find  correct location of some person or how many students have marks more than a particular marks or less than that when marks are given in unsorted manner.


Timing Difference :
> For a random input of size 124 inetgers.

bubble sort on average : 120 * 10^(-6) sec
merge  sort on average : 45 * 10^(-6) sec

merge sort is 3 times faster. 

5) Insertion Sort

There isn't much difference between Selection Sort and Insertion Sort.
 In selection sort, we select smallest number and place it at the front and then from N-1 numbers, we can select the smallest.

In insertion sort, we grow our list by 1 number at each step.
In 1st step, we have only 1 element and it is sorted, as it is only element.
In second step our list size is 2 , and we find correct position of 2nd element.
In third step our list size is 3, and now we find correct position of 3rd element.

Time complexity is O(n^2).
Space Complexity : No additional space is needed, operation is done on same input array.

Quicksort can be run parallel, as after each step, we have two subset which we have to sort.
Whereas in all the others Sorting so far, we cannot divide our input.

 
Bubble sort goes well with ARRAY. In LL, it will be difficult to traverse LL.
Insertion sort goes well with LINKED LIST, it will be overhead to move array elements to make space for each insertion.
Selection Sort again is better with Array, as with LL have to break and make connection.
QuickSort is better with Array.