1. 정의
퀵 정렬(Quick Sort)은 가장 빠른 정렬 알고리즘으로 알려져 있으며, 많이 사용되고 있다.
2. 방식
퀵 정렬은 피벗(pivot) 이라고 하여, 배열을 두 분류로 나누도록 한다. 피벗 앞에는 피벗보다 작은 배열 원소값이 들어가게 해야 하며 피벗 뒤에는 피벗보다 큰 배열 원소 값들이 들어가도록 해야 한다. 피벗을 이용한 배열 분할은 재귀 함수를 통해 지속적으로 반복해야 한다.
처음에는 피벗을 임의의 위치로 정한다. 그러면 배열이 2개의 partition 으로 분할된다. 이 때 배열의 첫 원소와 마지막 원소를 각각 start, end로 지정한다.
start는 pivot 보다 값이 작으면 건너뛰고, end는 pivot 보다 값이 크면 건너뛴다. 만약 start가 pivot보다 값이 큰 값이 매칭되면 일단 대기하고 end도 pivot보다 값이 작으면 대기한다. 그러면 start와 end의 값을 swap 해주는 방법이다.
swap 한 이후에는 start와 end 지점을 옮기도록 한다. 추후 start와 end가 서로 정한 범위를 벗어난 경우, Loop를 빠져나가게 된다.
3. 구현
이정도로 알아보고 코드로 구현해 보도록 하자.
public class Main {
public static void main(String[] args) {
int[] array = {22, 5, 11, 32, 120, 68, 70, 6, 8, 1};
Quick_Sort(array, 0, array.length - 1);
System.out.print("실행 결과 : ");
for(int k : array) System.out.print(k + " ");
}
public static void Quick_Sort(int[] A, int front, int back) {
int start = front;
int end = back;
int pivot = A[(front + back) / 2]; // pivot의 위치를 대략 가운데로 임의로 정한다.
do {
while (A[start] < pivot) start++; // 만약 start가 pivot 보다 작은 경우 ==> 포인터를 옮겨 준다.
while (A[end] > pivot) end--; // 만약 end가 pivot 보다 큰 경우 ==> 포인터를 옮겨 준다.
if (start <= end) {
// 이 경우에는 while 문에서 swap를 위해 대기중인 상황이다. 따라서, swap 시켜준 후 start를 1 up, end를 1 down 시켜줘야 한다.
int temp = A[end];
A[end] = A[start];
A[start] = temp;
start++;
end--;
}
} while(start <= end); // end가 start보다 더 작을 순 없다. 이 상태에서 반복을 계속한다.
if(front < end) Quick_Sort(A, front, end); // part 하나가 끝났다면 다음 part를 위해 재귀를 사용한다.
if(back > start) Quick_Sort(A, start, back); // part 하나가 끝났다면 다음 part를 위해 재귀를 사용한다.
}
}실행 결과 : 1 5 6 8 11 22 32 68 70 120실행 결과와 코드는 위와 같다. 퀵 정렬을 사용하기 위해서는 pivot을 임의로 설정(가운데로 할수록 좋다.)하고 좌, 우의 정렬을 pivot을 기준으로만 실행한 뒤 재귀를 실행하는 형식이다. 계속 part를 분할하다가 하나만 남을때 까지 part를 분할하므로 31, 32번 라인 조건문의 조건을 front < end 와 back > start로 설정한 것이다.
4. 결론
이러한 퀵 정렬은 시간복잡도를 평균 O(nlogn) 으로 가지며, 최악의 경우에는 O(n²) 으로 갖게 된다.
이상 퀵 정렬 정리를 마치도록 한다.
