1 files changed, 55 insertions, 0 deletions
diff --git a/week2/Quicksort.cs b/week2/Quicksort.cs
new file mode 100644
index 0000000..0cfa360
--- /dev/null
+++ b/week2/Quicksort.cs
@@ -0,0 +1,55 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace ALGA {
+	public class Quicksort {
+		public static void quicksort(ISortList list) {
+			quicksort(list, 0, list.Count - 1);
+		}
+
+		private static void quicksort(ISortList list, int leftIndex, int rightIndex) {
+			if (leftIndex >= rightIndex || leftIndex < 0) return;
+
+			int pivotIndex;
+			int middle = leftIndex + ((rightIndex - leftIndex) / 2);
+
+			// // Quicksort
+			// pivotIndex = leftIndex;
+
+			// pass unit tests
+			pivotIndex = middle;
+
+			// // Quicksort3
+			// List<Tuple<int, int>> picks = new List<Tuple<int, int>> {
+			// 	new Tuple<int, int>(leftIndex, list[leftIndex]),
+			// 	new Tuple<int, int>(middle, list[middle]),
+			// 	new Tuple<int, int>(rightIndex, list[rightIndex]),
+			// };
+			// picks.Sort((a, b) => a.Item2.CompareTo(b.Item2));
+			// pivotIndex = picks[1].Item1;
+
+			pivotIndex = partition(list, pivotIndex, leftIndex, rightIndex);
+
+			quicksort(list, leftIndex, pivotIndex - 1);
+			quicksort(list, pivotIndex + 1, rightIndex);
+		}
+
+		public static int partition(ISortList list, int pivotIndex, int leftIndex, int rightIndex) {
+			while (true) {
+				while (list.compare(leftIndex, pivotIndex) < 0) leftIndex++;
+				while (list.compare(pivotIndex, rightIndex) < 0) rightIndex--;
+
+				if (leftIndex >= rightIndex) break;
+
+				list.swap(leftIndex, rightIndex);
+				if (leftIndex == pivotIndex)
+					pivotIndex = rightIndex;
+				else if (rightIndex == pivotIndex)
+					pivotIndex = leftIndex;
+			}
+			return pivotIndex;
+		}
+	}
+}
+