퀵 소트란?
퀵 소트는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.
퀵 소트는 정렬 알고리즘 중 가장 빠르다고 하여 붙여진 이름이다. pivot을 선택하여 비교하며 정렬을 수행하는데 pivot으로 선택한 수가 가장 작거나 가장 크다면 최악의 경우로 정렬 수행 시간이 가장 오래 걸린다. 하지만 가장 오래 걸리더라도 O(n^2)의 시간 복잡도를 가지며 이 최악의 경우만 제외한다면 평균적으로 O(nlogn)의 시간 복잡도를 가진다.
퀵 소트은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
1. 리스트에서 임의의 수를 pivot으로 정한다.
2. pivot앞에는 pivot보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 정렬한다.
3. pivot의 앞부분과 pivot의 뒷부분을 재귀적으로 반복하여 정렬이 완료될 때까지 반복한다.
(하나의 pivot으로 정렬을 완료하면 pivot의 위치는 고정된다.)
다음은 JAVA로 작성된 퀵 소트의 코드이다.
public class quickSort {
public static void main(String[] args) {
int arr[] = {1,3,6,2,8,2,5,9};
System.out.print("정렬전: ");
for(int i = 0; i< arr.length; i++) {
System.out.print(" " + arr[i]);
}
System.out.println();
quickSort(arr,0,arr.length-1);
System.out.print("정렬후: ");
for(int i = 0; i< arr.length; i++) {
System.out.print(" " + arr[i]);
}
}
static void quickSort(int []array,int first, int end) {
//선택한 pivot의 위치
int p;
if(first<end) {
//pivot을 정하고 그 원소의 위치를 돌려주는 함수를 호출
p = partition(array,first,end);
//재귀적으로 pivot의 앞부분, 뒷부분으로 나누어 정렬 수행
quickSort(array, first, p-1);
quickSort(array, p+1, end);
}
}
static int partition(int[] array, int first, int end) {
//정렬이 완료된 후 pivot이 옮겨질 위치를 저장하는 변수
int i = first;
//배열의 끝에 있는 원소를 pivot으로 선택
int pivot = end;
//임시 변수
int temp=0;
//시작부터 끝까지 정렬을 수행
for(int k=first;k<end;k++) {
if(array[k]<array[pivot]) {
temp = array[k];
array[k] = array[i];
array[i] = temp;
i++;
}
}
//정렬이 완료된 후 pivot을 해당 위치로 이동
temp = array[pivot];
array[pivot] = array[i];
array[i] = temp;
return i;
}
}
다음은 출력 결과이다.
