QuickSort Algorithm

Quick sort is a comparison sort. The working of  quick sort algorithm is depending on a divide-and-conquer strategy. A divide and conquer strategy is  dividing  an array  into two sub-arrays. Quick sort is one of the fastest and simplest sorting algorithm. The complexity of quick sort in the average case is  Θ(n log(n)) and in the  worst case is Θ(n2).

In quick sort algorithm pick an element from array of elements. This element is called the pivot. Then compare the the values from left to right until a greater element is find then swap the values. Again start comparison from right with pivot. When lesser element is find then swap the values. Follow the same steps until  all elements which are less than the pivot come before the pivot and all elements greater than the pivot come after it. After this partitioning, the pivot is in its last position. This is called the partition operation. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

Pros

• Extremely fast on average

Cons

• Fairly tricky to implement and debug
• Very slow in the worst case (but see notes)
• In the worst case, could cause a stack overflow

Example:
 
Input:12 9 4 99 120 1 3 10 13




Output:1 3 4 10 12 13 99 120

public class QuickSort{
  public static void main(String a[]){
    int array[] = {12,9,4,99,120,1,3,10,13};
    quick_srt(array,0,array.length-1); 
  }
  public static void quick_srt(int array[],int low, int n){
     int lo = low;
     int hi = n;
     if(lo >= n) {
       return;
     }
     int mid = array[(lo + hi) / 2];
     while(lo < hi) {
         while(lo<hi && array[lo] < mid) {
            lo++;
         }
         while(lo<hi && array[hi] > mid) {
            hi--;
         }
         if(lo < hi) {
            int T = array[lo];
            array[lo] = array[hi];
            array[hi] = T;
         }
     }
     if(hi < lo) {
        int T = hi;
        hi = lo;
        lo = T;
     }
     quick_srt(array, low, lo);
     quick_srt(array, lo == low ? lo+1 : lo, n);
  }
} 

Notes: If the middle element in the array is very large or very small, the sort becomes slower. To reduce the chances of this, you can take median of the first, middle and last elements and put it in the middle. In a degenerate case, Quick sort could also recurse to a very deep level and cause a stack overflow. One way to avoid this is to keep track of the level of recursion (e.g. by passing it as a parameter) and switch to a simpler sort (like selection sort) if the recursion is too deep.

Reference: roseindia

Merge Sort Algorithm

In merge sorting algorithm unsorted values are divided into two equal parts iteratively. Then merge both parts and sort it. Then again merge the next part and sort it. Do it iteratively until  the values are not in sorted order. In merge sorting the number of elements must be even. 

In merge sort split the array values in halves recursively until each half has only single  element. Merge the two 1/2 values together and sort the values. Do same steps iteratively until the values are not sorted. 

In comparison to Quicksort the divide part is simple in Mergesort while the merging take is complex.
Quicksort can sort "inline" of an existing collection, e.g. it does not have to create a copy of the collection while Mergesort requires a copy. 

Example:

 12,9,4,99,120,1,3,10
 


public class mergeSort{
  public static void main(String a[]){
     int i;
     int array[] = {12,9,4,99,120,1,3,10};
     mergeSort_srt(array,0, array.length-1);
  }
  public static void mergeSort_srt(int array[],int lo, int n){
     int low = lo;
     int high = n;
     if(low >= high) {
        return;
     }
     int middle = (low + high) / 2;
     mergeSort_srt(array, low, middle);
     mergeSort_srt(array, middle + 1, high);
     int end_low = middle;
     int start_high = middle + 1;
     while((lo <= end_low) && (start_high <= high)) {
         if(array[low] < array[start_high]) {
            low++;
         }else {
            int Temp = array[start_high];
            for(int k = start_high- 1; k >= low; k--) {
               array[k+1] = array[k];
            }   
            array[low] = Temp;
            low++;
            end_low++;
            start_high++;
         }
     }
  }
}

Reference: roseindia 

Selection Sort Algorithm

In selection sorting algorithm, find the minimum value in the array then swap it first position. In next step leave the first value and find the minimum value within remaining values. Then swap it with the value of minimum index position. Sort the remaining  values by using same steps. Selection sort  is probably the most intuitive sorting algorithm to invent.

The complexity of selection sort algorithm is in worst-case, average-case, and best-case run-time of Θ(n2), assuming that comparisons can be done in constant time.

Code description:
In selection sort algorithm to find the minimum value in the array. First assign minimum index in key (index_of_min=x). Then find the minimum value and assign the index of minimum value in key (index_of_min=y). Then swap the minimum value with the value of minimum index.
At next iteration leave the value of minimum index position and sort the remaining values by following same steps.

Working of the selection sort :
Say we have an array unsorted A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by selection sort algorithm to sort the values of an array . (Say we have a key index_of_min that indicate the position of minimum value)
1.Initial varaible  index_of_min=0;
2.Find the minimum value in the unsorted array.
3.Assign the index of the minimum value into index_of_min variable.
4.Swap minimum value to first position.
5.Sort the remaining values of array (excluding the first value).

Example:

int array[] = {12,9,4,99,120,1,3,10}; 
selectionSort(array, array.length);   

public static void selectionSort(int array[], int n){
  for(int x=0; x<n; x++){
     int index_of_min = x;
     for(int y=x; y<n; y++){
        if(array[index_of_min]<array[y]){
        index_of_min = y;
        }
     }
     int temp = array[x];
     array[x] = array[index_of_min];
     array[index_of_min] = temp;
  }
} 
Reference: roseindia 

Insertion Sort Algorithm

Insertion sorting algorithm is similar to bubble sort. But insertion sort is more  efficient than bubble sort because in insertion sort the elements comparisons are less as compare to bubble sort. In insertion sorting algorithm compare the value until  all the prior elements are lesser than compared value is not found. This mean that the all previous values are lesser than compared value. This algorithm is more efficient than the bubble sort .Insertion sort is a good choice for small values and for nearly-sorted values. There are more efficient algorithms such as quick sort, heap sort, or merge sort for large values.

Pros: 
1.It is simple to implement
2.It is efficient on (quite) small data values
3.It is efficient on data sets which are already nearly sorted.
4.If a backwards linear search is used, it is much faster on an partially sorted array.

Cons
On an array, insertion is slow because all the elements after it have to be moved up.

The complexity of insertion sorting is O(n) at best case of an already sorted array and  O(n²) at worst case .
  
Code description:
In insertion sorting take the element form left assign value into a variable. Then compare the  value with  previous values. Put  value so that values must be lesser than the previous values. Then assign  next  value to a variable and follow the same steps relatively until the comparison not reached to end of array.

Working of insertion sorting:

 
int array[] = {12,9,4,99,120,1,3,10};
insertionSort(array, array.length);  

public static void insertionSort(int array[], int n){
  for(int i = 1; i < n; i++){
      int j = i;
      int B = array[i];
      while ((j > 0) && (array[j-1] > B)){
          array[j] = array[j-1];
          j--;
      }
      array[j] = B;
  }

References: roseindia