❓ 퀵 정렬?!
퀵 정렬: 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘.
기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균적인 시간 복잡도는 O(nlogn).
- 퀵 정렬의 핵심 이론
pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다.- 퀵 정렬의 과정
1. 데이터를 분할하는 pivot을 설정한다.
2. pivot을 기준으로 아래의 과정을 거쳐 데이터를 2개의 집합으로 분리한다.
1) start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.
2) end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.
3) start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면,
start, end가 가리키는 데이터는 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.
4) start와 end가 만날때까지 1) ~ 3)을 반복한다.
5) start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면
만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.
3. 분리 집합에서 각각 다시 pivot을 선정한다.
4. 분리 집합이 1개 이하가 될 때까지 과정 1 ~ 3을 반복한다.❗️문제 분석하기
- 퀵 정렬을 구현해 주어진 수를 오름차순으로 정렬한 뒤, k번째 수 출력
- 퀵 정렬 알고리즘에서 K번쨰 수를 좀 더 빨리 구하기 위한 아이디어 고민
- 퀵 정렬 알고리즘을 구현하려면 먼저 pivot을 지정해야 함
- 어떤 값을 pivot으로 정하면 k번째 수를 더 빨리 구할 수 있을까?! 고민
- pivot 정하는 방법
ㄴ pivot == K: K번째 수를 찾은 것이므로 알고리즘을 종료한다.
ㄴ pivot > K: pivot의 왼쪽 부분에 K가 있으므로 왼쪽(S ~ pivot -1)만 정렬을 수행한다.
ㄴ pivot < K: pivot의 오른쪽 부분에 K가 있으므로 오른쪽(pivot + 1 ~ E)만 정렬을 수행한다.
- 데이터가 대부분 정렬되어 있는 경우 앞쪽에 있는 수를 pivot으로 선택하면 불필요한 연산이 많아짐
- 이 문제의 경우 배열의 중간 위치를 pivot으로 설정하고 접근❗️pseudo code
count (숫자의 개수)
numK (K번째의 수)
savedArray (숫자 데이터 저장 배열)
for (count 만큼 반복( {
savedArray 배열 저장하기
}
퀵 소트 실행
K번째 데이터 출력
* 별도 함수 구현
퀵 소트 함수 (시작, 종료, K) {
피벗 구하기 함수 (시작, 종료)
if (피벗 == K) {
종료
} else if (K < 피벗) {
퀵 소트 수행하기 (시작, 피벗 -1, K)
} else {
퀵 소트 수행하기 (피벗 + 1, 종료, K)
}
}
피벗 구하기 함수 (시작, 종료) {
데이터가 2개인 경우는 바로 비교하여 정렬
middle (중앙 값)
중앙 값을 시작 위치와 swap
피벗을 시작 위치 값 savedArray[S]로 저장
i (시작점), j (종료점)
while (i <= j) {
피벗보다 큰 수가 나올 때까지 i++
피벗보다 작은 수가 나올 때까지 j--
찾은 i와 j 데이터를 swap
}
피벗 데이터를 나눠진 두 그룹의 경계 index에 저장하기
경계 index 리턴
}
✨ solve
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int count = Integer.parseInt(st.nextToken());
int numK = Integer.parseInt(st.nextToken());
st = new StringTokenizer(in.readLine());
int[] savedArray = new int[count];
for (int i = 0; i < count; i++) {
savedArray[i] = Integer.parseInt(st.nextToken());
}
quickSort(savedArray, 0, count - 1, numK - 1);
System.out.println(savedArray[numK - 1]);
}
private static void quickSort(int[] A, int S, int E, int K) {
if (S < E) {
int pivot = partition(A, S, E);
if (pivot == K) {
return;
} else if (K < pivot) {
quickSort(A, S, pivot - 1, K);
} else {
quickSort(A, pivot + 1, E, K);
}
}
}
private static int partition(int[] A, int S, int E) {
if (S + 1 == E) {
if (A[S] > A[E]) {
swap(A, S, E);
return E;
}
}
int M = (S + E) / 2;
swap(A, S, M); // 중앙 값을 1번째 요소로 이동
int pivot = A[S];
int i = S + 1, j = E;
while (i <= j) {
while (j > S + 1 && pivot < A[j]) {
j--;
}
while (i <= E && pivot > A[i]) {
i++;
}
if (i <= j) {
swap(A, i++, j--);
}
}
// 피벗 데이터를 나눠진 두 그룹의 경계 index에 저장하기
A[S] = A[j];
A[j] = pivot;
return j;
}
private static void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
Active 🙌 Curious 🤔 Energetic 💪