Insertion Sort

Insertion sort is one of the most fundamental comparison based stable sorting algorithm. It is also known as playing card sort. It is based on a fundamental principle that a single element array is already sorted.  A two element array requires single comparison to sort it. A three element array can be visualized as two sub arrays (first with 2 elements and second with one element). So in each iteration, a new value is added to an already sorted sublist. 

a1 = {101}   // already sorted
a2 = {101, 2} // can visualize it as, add 2 to a already sorted sub-array having 101
       {2, 101} // one comparison required to put 2 in proper place
a3 = {101, 2, 5} // a new number added to a2
        {2, 101, 5}
        {2, 5, 101}  // put 5 in proper place

To visualize how it works, check out animation on wikipedia.

Java Implementation

/**
 * Insertion sort implementation
 * 
 * @author Siddheshwar
 *
 */
public class InsertionSort {
 /**
  * Insertion sort in ascending order
  * 
  * @param arr
  * @return arr
  */
 public int[] sort(int[] arr) {
  int tmp = 0;
  for (int i = 1; i < arr.length; i++) {
   for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
    tmp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = tmp;
   }
   print(arr);
  }
  return arr;
 }

 // print current state of array
 private void print(int[] arr) {
  System.out.println();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + "  ");
  }
 }

 public static void main(String[] args) {
  int[] arr = { 12, 11, 13, 5, 6 };
  InsertionSort is = new InsertionSort();
  arr = is.sort(arr);
  // is.print(arr);
 }
}

Output:

11  12  13  5  6  

11  12  13  5  6  

5  11  12  13  6  

5  6  11  12  13 

Performs ideal when array is nearly sorted or size is small. It can also be used as base sorting algorithm in recursive divide and conquer quick sort and merge sort algorithms.

Important Points

• If the array is already sorted, swapping will never be performed and hence time complexity will be O(n). Adaptive sorting algorithm. 
• Average and worst case time complexity is O(n^2). Space complexity is O(1)
• Worst performance when array is reverse sorted. 
• Not ideal approach if data is random.
• In the best case (when already sorted), all the elements are in proper place so it takes linear time. 
• In-efficient for value based data with large memory footprint as amount of memory shift/swap will be high. Performs good when sorting on pointer based data. 

References:
https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort

---

keep coding !

Using Comparator to change sort technique in Java

Java provides ability to sort an array (or collection ), if the contained type properly implements java.lang.Comparable<T> interface. If type is comparable; sort method from Arrays class can be used for sorting the container (array or collection). This same utility is used by Collections API as well. You can design a type keeping in mind a natural sorting techniques, but there could still be a possibility to sort it differently. In such scenario, it doesn't make sense to go back to the class and modify the definition of the method. Some time, it might not be even feasible (to modify the class)!

In this post, I will be mentioning how can we provide a different ordering technique (other than one provided by class). The approach discussed in the post is applicable for any type (inbuilt or custom); but to make it simpler, I have considered Java's inbuilt type, String. Let's start with an example :

 String[] country = { "India", "US", "France" };  
 Arrays.sort(country);  
 System.out.println(Arrays.toString(country));  
 // Output : [France, India, US]  

Above snippet is able to sort array of strings because String class implements Comparable interface (i.e. provides implementation of compareTo(..) method)
To sort collections; Collections.sort(..) can be used.

Providing Custom Comparison 

So default comparison provided by String class, sorts the array in ascending order. What if you have to sort the above array in descending order?
Now modifying the compareTo(..) method of the String class is out of question (ditto the case, if you using a type from a jar). 

This is where the need for alternative comparison or ordering technique arises. Java provides another interface java.util.Comparator<T> to impose ordering on some collection of objects. This interface has compare(..) method to compare two objects of same type. So, we can create a Comparator<String> instance and pass it to the sort method. 

 import java.util.Comparator;  
 public class MyComparator implements Comparator<String> {  
      @Override  
      public int compare(String o1, String o2) {  
           return o2.compareTo(o1);  
      }  
 }  

 MyComparator my = new MyComparator();  
 Arrays.sort(country, my);  
 System.out.println(Arrays.toString(country));  
 //Output : [US, India, France]  

Note that the compare method in MyComparator class is basically calling compareTo method provided by String class. It has just reversed the order to reverse sort the array.

Java provides an inbuilt method to sort a collection in reverse order. So we don't need to re-invent the wheel but we should be aware of the logic.
Arrays.sort(country, Collections.reverseOrder());

Above approach is bit verbose; we can use anonymous class to make it more compact.

 import java.util.Arrays;  
 import java.util.Comparator;  
 public class OverrideDefaultSort {  
      public static String[] reverseSort(String[] country) {  
           Comparator<String> c = new Comparator<String>() {  
                @Override  
                public int compare(String o1, String o2) {  
                     return o2.compareTo(o1);  
                }  
           };  
           Arrays.sort(country, c);  
           return country;  
      }  
      public static void main(String[] args) {  
           String[] country = { "India", "US", "France" };  
           String[] c = OverrideDefaultSort.reverseSort(country);  
           System.out.println("Reverse Ordering:" + Arrays.toString(c));  
      }  
 }  

Output:
Natural Orering:[France, India, US]
Reverse Ordering:[US, India, France]

So second argument of sort method can take any comparator. Also above code can be even compacted further and Comparator can be provided inline inside the sort method. Below snippet sorts the array by size (or length) of the String.

 Arrays.sort(country, new Comparator<String>(){  
   @Override  
   public int compare(String o1, String o2) {  
       return Integer.compare(o1.length(), o2.length());  
   }  
 });  

Output:
Sort by length:[US, India, France]

So, sort in as many ways as you may wish !!!

Quicksort Implementation

Quicksort is a divide-and-conquer algorithm which centers around efficiently choosing the pivot value from the input data set. Based on this pivot value, the list is divided into two sublists - the first sublist containing all values less than or equal to the pivot and the second sublist containing all values greater than the pivot. This procedure is recursively called on these two sub lists.

Wikipedia has an interesting animation.

Below algorithm sorts array in-place and without using any extra space ( except the temporary holder, tmp). The algorithm selects the first element of the array as pivot value, but you can choose any value as the pivot.

Java Implementation 

package algo;

/**
 * QuickSort implemention
 * 
 * @author Siddheshwar
 * 
 */
public class QuickSort {

 /**
  * This method actually partitions the array in two sub parts. Doing
  * recursively the same, sorts the array as well
  * 
  */
 static int[] partition(int[] a, int low, int high) {
  int pi = low;
  int pivot = a[pi];
  int i = low, j = high;

  while (i < j) {
   // i should not exceed the high bound
   while (a[i] <= pivot && i < high)
    i++;

   // j should not reduce below low bound
   while (a[j] > pivot && j >= i)
    j--;

   if (i < j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
   }
  }

  // j is the final position for pivot element
  int tmp = a[j];
  a[j] = pivot;
  a[pi] = tmp;
  pi = j;

  // just for testing
  logging(a, pi);

  // do the same for lower and higher sub arrays
  if (low < pi - 1) {
   partition(a, low, pi - 1);
  }
  if (pi + 1 < high) {
   partition(a, pi + 1, high);
  }

  return a;
 }

 /**
  * Print array after each iteration to see how this sort works
  * 
  */
 public static void logging(int[] a, int pi) {
  for (int t : a) {
   System.out.print(t + " ");
  }
  System.out.println("\nPivot index :" + pi + "; Pivot :" + a[pi]);
 }

 public static void main(String[] args) {
  // int[] a = {0,666,1, 10, 30, 5, 19, 10};
  // int[] a = {1,1,1,1,1,1,1};
  // int[] a = {1,2,1,2,1,2,1};

  int[] a = { 0, 666, 2, 2, 2, 2, 45, 2, 3, 3, 3, 3 };
  a = QuickSort.partition(a, 0, a.length - 1);

  System.out.println("\nsorted array");
  for (int t : a) {
   System.out.print(t + " ");
  }
 }
}

Output:
0 666 2 2 2 2 45 2 3 3 3 3
Pivot index :0; Pivot :0
0 3 2 2 2 2 45 2 3 3 3 666
Pivot index :11; Pivot :666
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :9; Pivot :3
0 3 2 2 2 2 3 2 3 3 45 666
Pivot index :8; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :7; Pivot :3
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :5; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :4; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :3; Pivot :2
0 2 2 2 2 2 3 3 3 3 45 666
Pivot index :2; Pivot :2

sorted array
0 2 2 2 2 2 3 3 3 3 45 666 

Important points

• Performance of the algorithm depends a lot on the choice of pivot value. If it divides the array in two almost equal sized array, run time complexity will be O(n log n). Worst case complexity for Quicksort is O(n^2).
• It also takes O(log n) stack space on an average.
• You can also consider using a stack to eliminate recursion.
• On a small array, Insertion Sort is faster than Quicksort. So you can consider using Insertion sort if the size of the array is small. 

References

http://algs4.cs.princeton.edu/23quicksort/

--
keep coding !!!