📚 Quick Sort

Top-Down 재귀적 알고리즘을 이용하는 정렬 방법.
피벗 값을 기준으로 왼쪽과 오른쪽을 약하게 정렬된 상태로 만들고 재귀적으로 내려가면서 정렬을 완료한다. 이 떄 리스트의 왼쪽에는 피벗 값보다 작은 값만 나타나도록 하고, 오른쪽에는 피벗 값보다 큰 값만 나타나도록 한다. 그러면 마지막 단계에 이르렀을 때는 작은 각각의 배열이 모두 정렬되어 있으므로 최종적으로 정렬된다.

💻 구현

class QuickSort {
	public static void main(String[] args) {
		int[] arr = {5, 2, 4, 7, 1, 6};

		QuickSort(arr, 0, arr.length-1);
		for (int i=0;i<6;i++) System.out.print(arr[i] + " ");
	}

	public static void QuickSort(int[] arr, int start, int end) {
		if (start >= end) return;
		int pivot = partition(arr, start, end);
		QuickSort(arr, start, pivot-1);
		QuickSort(arr, pivot, end);
	}

	public static int partition(int[] arr, int start, int end) {
		int pivot;

		pivot = arr[(start+end)/2];
		while (start <= end) {
			while (arr[start] < pivot)
				start++;
			while (arr[end] > pivot)
				end--;
			if (start <= end) {
				swap(arr, start, end);
				start++;
				end--;
			}
		}
		return (start);
	}

	public static void swap(int[] arr, int a, int b) {
		int tmp;

		tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}

⌛️ Time Complexity

최악의 케이스에는 O(n^2)이지만, 평균적으로 O(nlogn) 이다.
이미 정렬된 상태에서는 분할이 한 칸의 배열씩 되므로 최악의 정렬도를 가지고,
이상적으로 반씩 나뉠 경우에 O(nlogn)의 복잡도를 가진다.
logn번 나뉘고, n번의 비교가 진행되기 때문.

보통 Insertion, Bubble, selection과 merge에 비해 가장 빠르다.

Is this stable?

stable하지 않다. 서로 떨어진 요소 간 교환이 일어나기 때문.