Quick sort algo implemented

vikitripathi · vikitripathi · commit 90db60bc47b9 · 2014-09-21T02:13:23.000+05:30
diff --git a/SortingAlgorithms/MergeSort/MergeBU.java b/SortingAlgorithms/MergeSort/MergeBU.java
@@ -0,0 +1,60 @@
+//Bottom-up mergesort: Java implementation
+public class MergeBU
+{
+private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
+{ 
+  assert isSorted(a, lo, mid);
+	// precondition: a[lo..mid] sorted
+  assert isSorted(a, mid+1, hi); // precondition: a[mid+1..hi] sorted
+   for (int k = lo; k <= hi; k++)
+	   aux[k] = a[k];
+   int i = lo, j = mid+1;
+   for (int k = lo; k <= hi; k++)
+   {
+	   if 	   (i > mid)               a[k]=aux[j++];
+	   else if (j > hi)                a[k]=aux[i++];
+	   else if (less(aux[j], aux[i]))  a[k]=aux[j++];
+	   else                            a[k]=aux[i++];
+   }
+  assert isSorted(a, lo, hi);
+   
+}
+private static boolean isSorted(Comparable[] a, int lo, int hi) {
+    for (int i = lo + 1; i <= hi; i++)
+        if (less(a[i], a[i-1])) return false;
+    return true;
+}
+private static boolean less(Comparable v, Comparable w)
+{ 
+	return (v.compareTo(w) < 0);
+}
+//private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
+//{
+//if (hi <= lo) return;// improve this by using insertion sort
+//int mid = lo + (hi - lo) / 2;
+//sort(a, aux, lo, mid);
+//sort(a, aux, mid+1, hi);
+////another improvement 
+//// if (!less(a[mid+1], a[mid])) return;
+//merge(a, aux, lo, mid, hi);
+//}
+public static void sort(Comparable[] a)
+{
+	int N = a.length;
+	Comparable[] aux = new Comparable[N];
+	for (int sz = 1; sz < N; sz = sz+sz)
+	for (int lo = 0; lo < N-sz; lo += sz+sz)
+	merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
+}
+//Client
+public static void main(String[] args){
+//	  int[] a={4,2,5,2,65,1,6,3,7,2};
+	  String[] a={"cat","abh","viki","shy","rom"};
+	  for(int p=0;p<5;p++)
+		  System.out.print(a[p]+",");
+	  System.out.println("");
+	  sort(a);
+	  for(int p=0;p<5;p++)
+		  System.out.print(a[p]+",");
+}
+}
diff --git a/SortingAlgorithms/QuickSort/Quick.java b/SortingAlgorithms/QuickSort/Quick.java
@@ -0,0 +1,51 @@
+//Quick Sort implementation 
+public class Quick
+{
+private static int partition(Comparable[] a, int lo, int hi)
+{ 
+	int i = lo, j = hi+1;
+	while (true)
+	{
+	while (less(a[++i], a[lo]))
+		if (i == hi) break;
+	while (less(a[lo], a[--j]))
+		if (j == lo) break;
+	if (i >= j) break;
+	exch(a, i, j);
+	}
+	exch(a, lo, j);
+	return j;
+}
+private static boolean less(Comparable v, Comparable w)
+{ 
+	return (v.compareTo(w) < 0);
+}
+private static void exch(Comparable[] a, int i, int j)
+{ 
+	Comparable swap = a[i];
+    a[i] = a[j];
+    a[j] = swap; 
+}
+public static void sort(Comparable[] a)
+{
+StdRandom.shuffle(a);//shuffle needed for performance guarantee
+sort(a, 0, a.length - 1);
+}
+private static void sort(Comparable[] a, int lo, int hi)
+{
+if (hi <= lo) return;
+int j = partition(a, lo, hi);
+sort(a, lo, j-1);
+sort(a, j+1, hi);
+}
+public static void main(String[] args){
+//	  int[] a={4,2,5,2,65,1,6,3,7,2};
+	  String[] a={"cat","abh","viki","shy","rom"};
+	  for(int p=0;p<5;p++)
+		  System.out.print(a[p]+",");
+	  System.out.println("");
+	  sort(a);
+	  for(int p=0;p<5;p++)
+		  System.out.print(a[p]+",");
+}
+}
