Insertion Sort

Problem Statement:
    Implement and Discuss Insertion Sort

Solution:

Insertion Sort is one of the basic sorting techniques , which is simple but inefficient in sorting large amount of data as compared to Quick Sort, Merge Sort , Heap Sort etc ..

However Insertion sort has a number of advantages:

1. Adaptive: i.e. efficient for data sets that are already substantially sorted.
           Time Complexity : O(n+d) , where d is the number of inversions.
2. Stable: does not change the relative order of elements with equal keys
3. In-Place : no additional space required.
4. Online : can sort as it receives the data.
5. More efficient than other quadratic algorithms O(n^2) like , Selection Sort and Bubble Sort,
     best case is O(n) for insertion sort and worst case is O(n^2)
     
Humans usually sort the deck of cards using insertion sort.

Concept Involved:
   For every iteration the element picked is inserted into its correct position in the already sorted array, for N element each element is picked and placed to its correct position. 

Full Source Code: LINK


Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

/** * Insertion Sort Subroutine */ public int[] insertionSort(int[] arr) { int size = arr.length; for(int i=1;i<size;i++){ int j=i; int num=arr[i]; while(j>0 && arr[j-1] > num){ arr[j]=arr[j-1]; j--; } arr[j]=num; } return arr; }

Steps involved in sorting the given sequence:
   Sequence : {3, 7, 4, 9, 5, 2, 6, 1}
 

Fig: Sorting of 30 element array

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Below is another graphical representation of intermediate step
of insertion sort.

Fig: Steps involved in Insertion Sort

References: Wikipedia
Try writing code for insertion sort by yourself
Please comment and post your suggestions.

Happy Coding!! :)

Topological Sorting

Problem Statement:
        Implement Topological Sorting, for the given Directed Acyclic Graph (DAG)

Fig: Directed Acyclic Graph(DAG)

Solution :

Note: Graph should be Directed Acyclic Graph (DAG)

Full Source Code : Link

What is Topological ordering or topological sort ?

Topological Sorting aka Toposort or Topological Ordering of a directed graph is a linear ordering of its vertices .i.e. all the directed edges of the graph should go forward in the ordering.

You can consider an example of Semester courses where you have a lot a courses to study but there are few per-requisite course required before you attempt for advanced ones.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

The topological sort of the given above graph would produce the given below figure in which all the edges go forward.

Fig: DAG , in which all edges go forward

  ///======== TOPOLOGICAL SORT ========/////////
 // to keep track of ordering
 private int currentLabel;
 int[] sortedArray;
 public void topologicalSort()
 {

  currentLabel=vistedStatusList.size()-1;
  sortedArray=new int[numVertices];

  Set<Map.Entry<Integer, Boolean>> set=vistedStatusList.entrySet();
  Iterator<Map.Entry<Integer, Boolean>> iterator=set.iterator();
  while(iterator.hasNext())
  {
   Map.Entry<Integer,Boolean> node= iterator.next();
   int key=node.getKey();
   boolean isVisited=vistedStatusList.get(key);
   if(!isVisited)
    topologicalSortUtil(key); // Call DFS for a given node , if unvisited
  }

  // printing the topological sorted array
  for(int i=0;i<sortedArray.length;i++)
  {
   if(sortedArray[i]!=0)
    System.out.print(sortedArray[i]+"\t");
  }
 }


 /**
  * Procedure Similar to DFS, unwinds when deepest node is encountered
  * @param vertex
  */
 public void topologicalSortUtil(int vertex)
 {
  vistedStatusList.put(vertex,true);
  List<Integer> list=adjList.get(vertex);

  if(list!=null)
  {
   int size= list.size();
   for(int i=0;i <size; ++i)
   {
    int adjNode=list.get(i);
    boolean isVisited=vistedStatusList.get(adjNode);
    if(!isVisited)
    {
     //System.out.println(adjNode + "\t");
     topologicalSortUtil(adjNode);
    }
   } 
  }
  /* for loop will end when the sink vertex is reached , that sink vertex is plucked and put in the array as per the currentLabel, 
   * which corresponds to its position in topological sort */
  sortedArray[currentLabel]=vertex;
  currentLabel--;
 }
  

Time Complexity : O(m+n)
where m: number of edges
           n: number of vertices

Please post comments and suggestions.

Happy Coding !! :)

QuickSort

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

import java.util.Arrays; /** * 3way quick sort in order to improve performance in case of too many duplicates , where normal * Quicksort subrouites averages to quadratic performance * @author Prateek * */ public class ModifiedQuickSort { private int arr[]; private int size; public static void main(String[] args) { int []testInput={6,3,6,4,2,6,8,2}; ModifiedQuickSort mdqs=new ModifiedQuickSort(); mdqs.sort(testInput); } public void sort(int input[]) { arr=input; size=input.length; modified3wayQsort(0,size-1); System.out.println(Arrays.toString(arr)); } /** * 3 WayQuick Sort * @param low * @param high */ void modified3wayQsort(int low,int high) { if(high <= low) return ; int l=low,r=high; int v=arr[low]; // Partioning element 1st element int pivot=l+1; while(pivot<=r) { if(arr[pivot] < v) { swap(pivot++,l++); } else if(arr[pivot] > v) { swap(pivot,r--); } else pivot++; } modified3wayQsort(low, l-1); modified3wayQsort(r+1, high); } /** * Swapping content * @param i * @param j */ private void swap(int i,int j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }

Merge Sort

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

import java.util.Arrays; /** * MergeSort using recursive and non recursive calls (bottom up mergesort) * @author Prateek * */ public class MergeSort { int arr[]; int size; public static void main(String[] args) { int []testInput={6,3,7,1,5,4,9,8,2}; MergeSort m=new MergeSort(); m.sort(testInput); } /** * * @param values */ public void sort(int values[]) { this.arr=values; this.size=arr.length; //TODO : uncomment if recursive call required //mergeSort(0, size-1); // recusive call bottomUpMergeSort(); // Non recursive call System.out.println("Sorted Array : " +Arrays.toString(arr)); } /** * * @param low * @param high */ private void mergeSort(int low, int high) { if (low < high) { int mid = low + (high - low) / 2; mergeSort(low, mid); mergeSort(mid + 1, high); merge(low, mid, high); } } /** * Non recursive merge sort */ private void bottomUpMergeSort() { // number of elements to be considered, and it doubles in the next pass for(int len=1;len<size ; len=len+len) { // for a given number of items traverse in pairs to call merge subroutine for(int index=0;index< size- len; index += len+len) { merge(index, index+len -1, Math.min(index + len + len -1 , size -1 )); } } } /** * Merge Subroutine * @param low : lower index of the array * @param middle : Middle index of the array * @param high : Last index of the array to be sorted */ private void merge(int low, int middle, int high) { int i=low; // initial index of 1st part of array int j=middle+1; // initial index of 2nd part of array int k=0; // index for auxillay array int temp[]=new int[size]; //auxillay Array // Copying the smalller of the two elements int the two parts while(i<=middle && j<=high) { if(arr[i] < arr[j]) { temp[k]=arr[i]; i++; } else { temp[k]=arr[j]; j++; } k++; } // simply 1st part of array copying if 2nd part gets exausted while(i<=middle) { temp[k]=arr[i]; i++; k++; } // simply 2nd part of array copying if 1st part gets exausted while(j<=high) { temp[k]=arr[j]; j++; k++; } // copying content from auxillay array to the original array k=0; while(low<=high) { arr[low]=temp[k]; k++; low++; } } }