2.3.1 Simple sort

• Write Max and Insert functions to help to organize your algorithm
• All sort algorithm don’t compare equal relationship. So some algorithm is Stable, and other is not stable
• Bubble is simple source code stable sorting.
• All the sorting is from minimum to maximum.

1. for all sort comparsion, there is good ref website: https://www.toptal.com/developers/sorting-algorithms/selection-sort
2. Selection sort is an in-place comparison sort. O(n2). The algorithm finds the minimum value, swaps it with the value in the first position. And repeat From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic.

   However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

   For(int size=n ;size>1;size--){ 
   Int j = Max(a,size); 
   Swap(a[j],a[size-1]); 
   }
3. Insertion sort is suitable for small list and mostly sorted list. Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

   For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

   For(int I = 0;i<n;i++){ 
   Int iv = a[i]; 
   Insert(a,I, iv); 
   } 
   Insert(a[],int n,int lv){ 
   For(int I = n-1;i>=0&&lv<a[i];i--) 
       A[i+1]=a[i]  //move each element from tail to head one by one 
   A[i]  = lv;  //insert here. 
   }
4. Bubble sort is stable
   For (int I = n;i>0;i--){ 
           For(int j= 0;j<I;j++) 
                   If(a[j]<a[j+1]) swap(a[j],a[j+1]); 
   }
5. Bubble sort can stops after reaching a sorted array. In the best case (already sorted), every insert requires constant time. So Bubble and insert can reach O(n) time in Best context. Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).
6. Selection sort only need O(n) write, so if write is expensive operation, you need to use it.