Sorting

• Bubble Sort

It works by iterating the input array from the first element to the last, comparing each pair of elements and swapping them if needed.

Complexity : n2

Algorithm -> A[] and size

• pass , i;
• for ( pass = size-1 ; pass > 0; pass--)
• for (i = 0; i<pass ; i++)
• if(A[i] > A[i+1])
• Swap A[i] and A[i+1] with the help of temp variable

Algorithm takes O( n2) (even in best case). We can improve it by using one extra flag. See below program for implementation with flag = swapped
BubbleSort Program

Best Case complexity of improved version is O(n)

Advantage 

• It can detect whether the input array/list is already sorted or not

• Selection Sort

  This algorithm is called selection sort since it repeatedly selects the smallest element. Selection sort is an in-place sorting algorithm. It comes under greedy algorithm because at each step it tries to find the min, though being greedy does not mean that it will result in optimal solution
  See Program
  
  Complexity : n2
  
  Algorithm -> A[] and size
• int i , j , min , temp
• for( i = 0 ; i <= size-1 ; i++)
• min = i
• for( j = i+1 ; j < size ; j++)
• if A[j] < A[min]
• min = j
• swap A[i] and A[min] using temp

Advantage

•  In place sorting

• Insertion Sort

   

  Advantage

  • In-place: It requires only a constant amount O( 1) of additional memory space 
  • Online: Insertion sort can sort the list as it receives it

• Merge Sort:

• Merging is the process of combining two sorted files to make one bigger sorted file.
  
• In Quick sort most of the work is done before the recursive calls. Quick sort starts with the largest subfile and finishes with the small ones and as a result it needs stack. Moreover, this algorithm is not stable. Merge sort divides the list into two parts; then each part is conquered individually. Merge sort starts with the small subfiles and finishes with the largest one. As a result it doesn’t need stack. This algorithm is stable.
• See code