Implement Quick Sort and Fuzzy Sort

lgrcyanny · Aug 8, 2013 · c3894f7 · c3894f7
1 parent a2080bc
commit c3894f7
Show file tree

Hide file tree

Showing 2 changed files with 157 additions and 1 deletion.
diff --git a/src/com/algorithm/quicksort/FuzzySort.java b/src/com/algorithm/quicksort/FuzzySort.java
@@ -0,0 +1,108 @@
+package com.algorithm.quicksort;
+
+public class FuzzySort {
+	private Interval[] data = null;
+
+	public FuzzySort(Interval[] data) {
+		if (data != null) {
+			this.data = data;
+		}
+	}
+
+	private int[] partition(int p, int r) {
+		Interval pivot = data[r];
+		int i = p;
+		int j = p;
+		int k = r;
+		while (j <= k) {
+			if (data[j].compareTo(pivot) > 0) {
+				// When current item is totally bigger than pivot, 
+				// exchange them, and decrease the upper bound k by 1
+				exchange(j, k);
+				k--;
+			} else if (data[j].compareTo(pivot) < 0) {
+				// When current item is totally smaller than pivot, 
+				// exchange i, j
+				exchange(i, j);
+				i++;
+				j++;
+			} else {
+				// When overlap, replace the pivot by the overlap Interval
+				double begin = data[j].begin > pivot.begin ? data[j].begin : pivot.begin;
+				double end = data[j].end < pivot.end ? data[j].end : pivot.end;
+				pivot = new Interval(begin, end);
+				j++;
+			}
+		}
+		return new int[] {i, k};
+	}
+
+	public void quicksort(int p, int r) {
+		if (p < r) {
+			int[] q = partition(p, r);
+			quicksort(p, q[0] - 1);
+			quicksort(q[1] + 1, r);
+		}
+	}
+
+	public void prdoubleData() {
+		for (Interval obj : data) {
+			System.out.println("[" + obj.getBegin() + " , " + obj.end + "]");
+		}
+		System.out.println("=========");
+	}
+
+	private void exchange(int i, int j) {
+		Interval temp = data[i];
+		data[i] = data[j];
+		data[j] = temp;
+	}
+
+
+	public static class Interval implements Comparable<Interval >{
+		private double begin;
+		private double end;
+		public Interval(double begin, double end) {
+			this.begin = begin;
+			this.end = end;
+		}
+		public double getBegin() {
+			return begin;
+		}
+		public void setBegin(double begin) {
+			this.begin = begin;
+		}
+		public double getEnd() {
+			return end;
+		}
+		public void setEnd(double end) {
+			this.end = end;
+		}
+		@Override
+		public int compareTo(Interval another) {
+			if (this.begin >= another.end) {
+				return 1;
+			} else if (this.end <= another.begin) {
+				return -1;
+			} else {
+				return 0;
+			}
+		}
+	}
+
+	public static void main(String[] args) {
+		Interval[] data = new Interval[6];
+		data[0] = new Interval(1, 2);
+		data[1] = new Interval(0.5, 1);
+		data[2] = new Interval(3, 4);
+		data[3] = new Interval(7.5, 8);
+		data[4] = new Interval(0.5, 8);
+		data[5] = new Interval(4, 5);
+//		data[6] = new Interval(4, 5);
+		FuzzySort mySort = new FuzzySort(data);
+		mySort.prdoubleData();	
+		mySort.quicksort(0, data.length - 1);
+		mySort.prdoubleData();	
+	}
+
+}
diff --git a/src/com/algorithm/quicksort/QuickSort.java b/src/com/algorithm/quicksort/QuickSort.java
@@ -24,6 +24,32 @@ private int partition(int p, int r) {
 		return i + 1;
 	}
 
+	private int partitionHoare(int p, int r) {
+		int i = p;
+		int j = r;
+		int pivot = data[p];
+		while (i != j) {
+			while (i < j && data[j] > pivot) j--;
+			if (i < j) {
+				data[i] = data[j];
+				i++;
+			}
+			while (i < j && data[i] < pivot) i++;
+			if (i < j) {
+				data[j] = data[i];
+				j--;
+			}
+		}
+		data[i] = pivot;
+		return i;
+	}
+
+	private int randomPartition(int p, int r) {
+		int pivot = (int) Math.random() * (r - p + 1) + p;
+		swap(pivot, data[r]);
+		return partition(p, r);
+	}
+
 	private int partitionForReversedOrder(int p, int r) {
 		int pivot = data[r];
 		int i = p - 1;
@@ -58,6 +84,27 @@ public void quickSort(int p, int r, boolean assending) {
 		}
 	}
 
+	public void quickSortRandom(int p, int r, boolean assending) {
+		if (p < r) {
+			int q;
+			if (assending) {
+				q = randomPartition(p, r);
+			} else {
+				q = partitionForReversedOrder(p, r);
+			}
+			quickSort(p, q - 1, assending);
+			quickSort(q + 1, r, assending);
+		}
+	}
+
+	public void quickSortHoare(int p, int r) {
+		if (p < r) {
+			int pivot = partitionHoare(p, r);
+			quickSortHoare(p, pivot - 1);
+			quickSortHoare(pivot + 1, r);
+		}
+	}
+
 	public void printData() {
 		for (int val : data) {
 			System.out.println(val);
@@ -68,7 +115,8 @@ public void printData() {
 	public static void main(String[] args) {
 		int[] data = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};
 		QuickSort mySort = new QuickSort(data);
-		mySort.quickSort(0, data.length - 1, true);
+		//mySort.quickSortRandom(0, data.length - 1, true);
+		mySort.quickSortHoare(0, data.length - 1);
 		mySort.printData();
 	}