📁퀵 정렬
기준 값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하는 정렬로 정렬 알고리즘 중 가장 빠른 속도를 자랑하며 분할 정복(Divide and Conquer) 알고리즘을 따른다.
1️⃣ 퀵 정렬의 과정
-
pivot 값을 선정한다.
-
분할(Divide) : 입력 배열을 pivot을 기준으로 비균등하게 2개의 서브 리스트로 분할한다.
-
정복(Conquer) : 서브 리스트를 정렬한다. 서브 리스트의 크기가 조금 크다고 생각이 들면 재귀 호출을 이용해 다시 분할 정복 방법을 적용한다.
-
결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = new int[] {38, 27, 43, 3, 9, 82, 10, 22};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void quickSort(int[] arr, int low, int high) {
if(low >= high) {
return;
}
// pivot 값 선정
int pivot = low + (high - low) / 2;
int pivotValue = arr[pivot];
int left = low;
int right = high;
// pivot을 기준으로 왼쪽과 오른쪽 자리 변경(pivot보다 왼쪽은 작게 오른쪽은 크게)
while(left <= right) {
// 자리 교환을 위해 left에 pivot보다 큰 값을 탐색
while (arr[left] < pivotValue) {
left++;
}
// 자리 교환을 위해 pivot보다 작은 값을 탐색
while (arr[right] > pivotValue) {
right--;
}
// left와 right 위치를 변경
if(left <= right) {
int tmp = arr[right];
arr[right] = arr[left];
arr[left] = tmp;
left++;
right--;
}
}
quickSort(arr, low, right);
quickSort(arr, left, high);
}
}2️⃣ 퀵 정렬 정리
-
퀵 정렬은 불안정 정렬(Unstable Sort)이다.
- 같은 값을 가지는 원소의 순서가 정렬 전과 동일하다는 보장을 하지 않는다.
-
제자리 정렬(In-Place Sort)이다.
- 입력 배열 내에서 정렬이 수행되므로 별도의 추가 메모리가 필요하지 않는다.
-
분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.
- 합병 정렬(merge sort)과 다르게 퀵 정렬은 리스트를 비균등하게 분할한다.
3️⃣ 정렬 알고리즘 시간복잡도 비교
4️⃣ 퀵 정렬 코딩테스트 예제
📌 문제 탐색하기
🌝 입력
- N과 K가 주어진다. (1 <= N <= 5,000,000), (1 <= K <= N)
- A1, A2, ..., An이 주어진다. (-10⁹ <= Ai <= 10⁹)
🌑 출력
A를 정렬했을 때, 앞에서부터 K번 째 있는 수를 출력한다.
🕔 시간제한
2초
🚨 접근
퀵 정렬을 활용해 정렬해보자.
- Java에서 제공하는 정렬을 하면 되지만 퀵 정렬 공부를 위해 퀵 정렬을 통해 정렬을 해보자.
🙆♂️ 가능한 시간복잡도
이중 반복 불가능
- N이 5,000,000이기 때문에 이중으로 반복을 수행하면 10¹² 이상의 시간이 소요되기 때문에 이중 반복은 불가능하다.
📌 문제 풀이
- quickSort를 재귀할 예정인데 이 때 수행을 중지할 조건을 명시하여 return을 해준다.
- pivot을 중간 값으로 둘 때 (low + high) / 2로 사용할 수 있지만 이는 low가 Integer.MAX_VALUE - 1, high가 Integer.MAX_VALUE일 경우 정수 오버플로우를 발생하기 때문에 low + (high - low) / 2를 사용한다.
- pivot의 위치가 변경될 가능성이 있으므로 배열에서 pivot 요소를 호출하는 것이 아닌 pivotValue는 저장해두고 사용한다.
- pivotValue보다 앞 쪽에 큰 값이 존재할 때까지 start를 증가시켜준다.
- pivotValue보다 뒷 쪽에 작은 값이 존재할 때까지 end를 감소시켜준다.
- start가 end보다 작거나 같으면 인덱스 start와 end의 위치를 변경시켜준다.
📌 정답 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
quickSort(arr, 0, arr.length - 1);
System.out.println(arr[k-1]);
}
static void quickSort(int[] arr, int low, int high) {
// 수행 중지 조건
if(low >= high) {
return;
}
// pivot을 중간 값으로 둘 때 (low + high) / 2는 정수 오버플로우를 발생하기 때문에
// low + (high - low) / 2 를 사용한다.
int pivot = low + (high - low) / 2; // 2
// pivot의 값이 변경될 수 있으므로 값을 저장해두고 사용한다.
int pivotValue = arr[pivot];
int start = low;
int end = high;
while(start <= end) {
while(pivotValue > arr[start]) {
start++;
}
while(arr[end] > pivotValue) {
end--;
}
if(start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
quickSort(arr, low, end);
quickSort(arr, start, high);
}
}