핵심이론
퀵정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘입니다
기준값이 어떻게 선정되는지가 시간복잡도에 많은 영향을 미치며, 평균 시간복잡도는 O(NlogN) 이며 최악의 경우 O(N^2)입니다
퀵 정렬의 동작방식은 다음과 같습니다
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법
이는 분할정복 방식에 속하며 병합정렬과 다른점은
병합정렬은 하나의 리스트를 ‘절반’ 으로 나누어 분할정복하고
퀵정렬은 피벗의 값에 따라 피벗보다 작은 값을 갖는 부분리스트와 피벗보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에 하나의 리스트에 대해 비균등하게 나뉜다는 점이 있다
퀵 정렬의 전체적인 과정은 이렇다.
1. 피벗을 하나 선택한다.
2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
3. 양 방향에서 찾은 두 원소를 교환한다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)
6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)
퀵정렬 구현
package org.example;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
}
public static void l_pivot_sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return;
}
/**
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬된 상태로
* 만든 뒤, 최종적으로 pivot의 위치를 얻는다
*
* 그리고 나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분 리스트로 나누어
* 분할정복을 한다다 */
int pivot = partition(a, lo, hi);
l_pivot_sort(a, lo, pivot - 1);
l_pivot_sort(a, pivot + 1, hi);
}
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left];
while (lo < hi) {
/**
* hi가 lo 보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 때까지 hi를 감소시킨다
*/
while (a[hi] > pivot && lo < hi) {
hi--;
}
/**
* hi가 lo보다 크면서 , lo의 요소가 pivot보다 큰 원소를
* 찾을때 까지 lo를 증가시킨다
*/
while (a[lo] <= pivot && lo < hi) {
lo++;
}
/**
* while loop문을 돌며 교환 해야 하는 인덱스가 정해지만
* 두 인덱스의 값을 교환한다
*/
swap(a, lo, hi);
}
/**
* 마지막으로 맨 처음 pivot으로 설정했던 위치 (a[left])의 원소와
* lo가 가리키는 원소를 바꾼다
*/
swap(a, left, lo);
return lo;
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
참고 - 퀵 정렬
