퀵 정렬(Quick Sort)

적절한 원소 하나를 기준(피벗, pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고, 그 뒤에 피벗을 옮겨 피벗보다 작은 것과 큰 것으로 나눈 뒤, 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬

→ unstable sort

시간복잡도

• 아래 그림들은 다크모드에서 정상적으로 보이지 않을 수 있습니다.

원소들이 랜덤 배열 되어있을 때, 원소들을 크기가 1인 조각으로 나누기 위해 필요한 순환 호출의 깊이는 $log\,n$이다. 크기가 1인 부분 배열을 각각 n번 비교해야 하므로 평균(or 최선) 시간복잡도는 $O(n\;log\,n)$이다.

만일 원소들이 반대로 오름차순 혹은 내림차순 되어있을 땐, 필요한 순환 호출의 깊이는 n이므로 최고 시간복잡도는 $O(n^2)$이 된다.

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며 공간 복잡도는 $O(1)$이다. 메모리 참조의 지역화가 되어있기 때문에 CPU 캐시의 히트율이 높아 효과적이다.

호어 파티션

pivot 값을 첫 번째 원소로 설정하는 알고리즘

코드 구현

import java.util.Arrays;

public class QuickSorting {
	public static void main(String[] args) {
		int[] arr = { 20, 32, 37, 17, 22, 8, 13, 42, 26 };
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int pivot = partition(arr, left, right);
			quickSort(arr, left, pivot - 1);
			quickSort(arr, pivot + 1, right);
		}
	}

	public static int partition(int[] arr, int left, int right) {
		int pivot = arr[left];

		int L = left + 1, R = right; // 시작구간은 left 한 칸 옆부터 끝까지
		int tmp;
		
		// 교차가 되는 순간 멈추기
		while (L <= R) {
			//L : pivot보다 큰 값을 찾을 때까지 이동
			while(L <= R && arr[L] <= pivot) {
				L++;
			}
			//R : pivot보다 작거나 같은 값을 찾을때 까지 이동
			while(arr[R] > pivot) {
				R--;
			}
			//L과 R의 값을 서로 바꾸기
			if(L<R) {
				tmp = arr[L];
				arr[L] = arr[R];
				arr[R] = tmp;
			}
		}
		
		//pivot이 가리키는 값과 R이 가리키는 값을 바꾸어 pivot의 위치를 결정
		tmp = arr[left];
		arr[left] = arr[R];
		arr[R] = tmp;
		
		return R;
	}

}

로무토 파티션

pivot 값을 마지막 원소로 설정하는 알고리즘

로무토 파티션에 대한 예제는 이 곳에서 확인할 수 있다.

코드 구현

import java.util.Arrays;

public class QuickSorting {
	public static void main(String[] args) {
		int[] arr = { 77, 32, 37, 17, 22, 8, 13, 42, 26 };

		quickSort(arr, 0, arr.length - 1);

		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int pivot = partition(arr, left, right);
			quickSort(arr, left, pivot - 1);
			quickSort(arr, pivot + 1, right);
		}
	}

	public static int partition(int[] arr, int left, int right) {
		int pivot = arr[right];
		int i = left - 1; // i : pivot 보다 작은 값들의 경계

		for (int j = left; j < right; j++) {
			if (arr[j] <= pivot) {
				i++;
				swap(arr, i, j);
			}
		}
		//pivot을 자기 위치로 보내기 위해서 swap
		swap(arr, i+1, right);
		return i+1;
	}

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

}

출처

---

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html
https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.2.2
https://underdog11.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Quick-Sort-%ED%80%B5%EC%A0%95%EB%A0%AC-%ED%95%84%EC%88%98-%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A6%AC-%EB%A1%9C%EB%AC%B4%ED%86%A0-%EB%B6%84%ED%95%A0-%ED%98%B8%EC%96%B4-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9D%B8-%ED%94%BC%EB%B4%87%EA%B0%92-%EC%A0%95%ED%95%98%EA%B8%B0
https://en.wikipedia.org/wiki/Quicksort