[Algorithm] 04.정렬 - 퀵정렬 (Quick sort)
오랜만에 다섯번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 정렬 알고리즘.
퀵 정렬에 대해 알아보겠습니다.
1. 데이터 중에서 피봇(pivot)을 뽑습니다.
2. 피봇을 제외한 데이터들을 피봇보다 작은 데이터, 큰 데이터로 분류합니다.
3. 이렇게 두 그룹으로 나뉜 데이터에서 같은 동작을 반복하여 정렬 될 때까지 실행합니다.
퀵 정렬은 설명만 들으면 이해가 되지만 어떻게 이 정렬이 NlogN시간에 정렬이 되는지,
그리고 코드로는 어떻게 작성할지 생각이 막막한 정렬법입니다.
그림과 함께 천천히 알아보도록 하겠습니다.
퀵정렬을 위해 피봇을 정해야합니다.
이번엔 데이터의 정렬되지 않은 그룹의 가장 앞 수를 피봇으로 정해보도록 하겠습니다.
피봇을 정하고 데이터를 순회하면서 피봇보다 작은 수와 큰 수로 나누어줍니다.
계속해서 그룹을 배치해주면...
한 번의 순회가 끝나면, 피봇은 자신의 정렬된 위치에 자리하게 됩니다.
예시 데이터에서 다섯번째로 작은 5는 자신 앞에 위치하는 자기보다 작은 수가 4개임이 당연하므로 자연스럽게 다섯번째 위치에 자리잡게 됩니다.
다음은 피봇으로 나누어진 그룹의 한 쪽에서 다시 한 번 피봇을 정해줍니다.
처음에 약속한대로 가장 앞의 데이터 3을 피봇으로 정합니다.
피봇보다 작은지 큰지에 따라 재배치하면 이런 모양이 됩니다.
5의 경우처럼, 이 그룹에서 세번째에 위치해야하는 3은 자신의 정렬된 위치에 도달한 것을 알 수 있습니다.
5보다 큰 쪽의 그룹도 피봇을 정하고 똑같이 재배치합니다.
두번째 순회가 끝났습니다.
같은 방식으로 1을 피봇으로 잡으면 현 상태 그대로 머물게 되고, 이후 2,4,6,8 하나씩이 남게 된 그룹은 그대로 정렬된 상태가 됩니다.
보시다시피 피봇을 한 번 정할때마다 데이터가 두개로 나뉘고, 전체 데이터를 한 번 순회하면 2^N-1개의 데이터가 정렬되면서 logN번의 순회를 마치면 정렬이 완료되게 됩니다.
한 번 순회할때 데이터를 N개씩 비교하므로 시간복잡도는 NlogN이 됩니다.
(실제로는 매 순회마다 일부 데이터가 완벽히 정렬되므로 비교하는 데이터는 N개보다 적습니다.)
퀵정렬이라는 이름처럼 빠르게 정렬이 완료되는것이죠.
하지만 이런 퀵 정렬에도 예외적인 상황이 있습니다.
이렇게 역순으로 정렬된 데이터를 퀵정렬한다고 생각해 봅시다.
피봇을 가장 앞의 수로 정하고, 순회해서 작은 수의 그룹을 만들었더니...
마치 버블정렬을 돌렸을 때처럼 피봇을 제외한 모든 수가 되었습니다!
같은 방식으로 피봇을 또 뽑게 되면 또다시 하나의 데이터만 정렬되게 되고, N-1번의 순회가 필요합니다.
그럼 피봇을 다른 방식으로 뽑는다면 어떨까요?
가장 앞의 수 대신 중앙의 수를 골라 피봇으로 선택했습니다.
비교 후엔 우리가 아까 테스트했던 퀵 정렬 처럼 두개의 그룹으로 나뉘며 정렬이 진행되는것을 볼 수 있습니다.
라이브러리에 구현되어 있는 퀵 소트는 이렇듯 피봇이 불리하게 뽑히는 것을 막기 위해 무작위 수로 피봇을 정하는 식으로 예외적인 상황을 회피한다고 합니다.
이렇게 퀵정렬을 통한 정렬이 완료되었습니다!
이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.
아래는 JAVA로 구현한 간단한 퀻정렬 코드와 테스트입니다!
이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.
import java.util.Arrays;
import java.util.Random;
public class sort_05_quick {
static int size = 10;
static int bound = 1000;
static int count = 0;
// 데이터의 갯수와 범위 설정
public static void main(String[] args) {
int[] data = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
data[i] = random.nextInt(bound);
}
// 랜덤 값 넣어주기
System.out.println(Arrays.toString(data));
// 랜덤하게 들어간 데이터 확인
//////////////// 퀵정렬 구현코드는 하단으로 /////////////////
quickSort(data, 0, data.length - 1);
//////////////////////////////////////////////////////
System.out.println(Arrays.toString(data));
System.out.println("비교횟수 : " + count);
}
private static void quickSort(int[] data, int left, int right) {
if (left < right) {
int i = left;
int j = right;
int pivot = data[(left + right) / 2];
while (i < j) {
while (j >= 0 && data[j] > pivot) {
j--;
}
while (i < j && data[i] < pivot) {
i++;
}
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
count++;
}
// 정렬 과정
quickSort(data, left, i - 1);
quickSort(data, i + 1, right);
}
}
}