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;
		}
	}
}