Quick Sort

Average: O(n log n)
Worst: O(n²)
n = size(array)

Python | Java

	def qsort(nums: List[int]) -> None:
	def qsort_helper(nums: List[int], l: int, r: int) -> None:
	if l >= r: return
	p = partition(nums, l, r)
	qsort_helper(nums, l, p - 1)
	qsort_helper(nums, p + 1, r)
	def partition(nums: List[int], l: int, r: int) -> int:
	pivot, p = nums[r], r
	i = l
	while i < p:
	if nums[i] > pivot:
	nums[i], nums[p - 1] = nums[p - 1], nums[i]
	nums[p], nums[p - 1] = nums[p - 1], nums[p]
	i -= 1
	p -= 1
	i += 1
	return p
	qsort_helper(nums, 0, len(nums) - 1)

view raw QuickSort.py hosted with ❤ by GitHub

	void qsort(int[] nums) {
	qsort(nums, 0, nums.length - 1);
	}
	void qsort(int[] nums, int l, int r) {
	if (l >= r) return;
	int p = partition(nums, l, r);
	qsort(nums, l, p - 1);
	qsort(nums, p + 1, r);
	}
	int partition(int[] nums, int l, int r) {
	int pivot = nums[r];
	int p = r;
	for (int i = l; i < p; i++) {
	if (nums[i] >= pivot) {
	swap(nums, i, p - 1);
	swap(nums, p, p - 1);
	i--;
	p--;
	}
	}
	return p;
	}
	void swap(int[] nums, int a, int b) {
	int tmp = nums[a];
	nums[a] = nums[b];
	nums[b] = tmp;
	}

view raw QuickSort.java hosted with ❤ by GitHub

Tricks

Quick Select