-
퀵 정렬(Quick Sort)자료구조와 알고리즘/기초 2020. 9. 19. 18:21
퀵 정렬은 합병 정렬과 함께 대표적인 분할 정복 알고리즘 중 하나이다. 여기서 분할 정복 알고리즘이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어 문제를 해결하는 알고리즘을 뜻한다. 퀵 정렬은 특정 값을 기준으로 작은 값과 큰 값을 나눈다. 이때의 기준값을 피벗(pivot)이라 한다. 예시를 통해 살펴보자.
예시
다음 숫자들을 오름차순으로 정렬하라.
1. 분할
오름차순으로 정렬하기 위해서는 피벗보다 작은 값은 피벗 왼쪽에 피벗보다 큰 값은 피벗의 오른쪽에 와야 한다. 그리고 이를 위해서 배열 양쪽에 포인터를 두고, 왼쪽 포인터는 피벗보다 큰 값이 나올 때까지 이동하고 오른쪽 포인터는 피벗보다 작은 값이 나올 때까지 왼쪽으로 이동하며 값을 교환한다.
아래 그림을 보면 왼쪽 포인터는 피벗보다 큰 값을 찾을 때까지 계속 오른쪽으로 이동하면서 8에서 멈추고, 오른쪽 포인터는 반대로 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동하다가 2에서 멈추게 된다. 이때 두 포인터에 위치한 값을 교환한다.
2. 분할 종료 시점
분할 종료 시점은 피벗을 기준으로 작은 값과 큰 값이 나눠질 때이다.
아래 그림을 보면 왼쪽 포인터는 이동하다가 7에서 멈춘다. 오른쪽 포인터는 피벗보다 작은 값을 찾기위해 이동하다가 왼쪽 포인터를 교차하게 된다. 이때 피벗보다 작은 값과 큰 값이 분리되었음을 확인할 수 있다. 마지막으로 피벗을 오른쪽 포인터의 값과 교환하면 피벗을 기준으로 분할이 완료된다
3. 재귀 호출
피벗은 이미 정렬된 상태이므로 피벗을 제외한 두 영역에 대해 재귀호출을 수행한다.
코드 구현
class Sort { private static void quickSort(int[] arr, int start, int end) { // 분할할 영역이 한 개 이하인 경우 if (start >= end) { return; } int pivot = arr[start]; // pivot을 첫 번째 값으로 설정한다. int left = start + 1; // 분할을 위한 왼쪽 포인터 int right = end; // 분할을 위한 오른쪽 포인터 while (left < right) { // pivot 보다 큰 값이 나타낼 때까지 우측으로 이동한다. while (arr[left] < pivot) left++; // pivot 보다 작은 값이 나타낼 때까지 좌측으로 이동하며, // right가 left보다 작아진 경우는 분할 대상이 더이상 없는 경우이다. while (arr[right] > pivot && left < right) right--; // 분할을 위해 서로 교환 if (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } } arr[start] = arr[right]; arr[right] = pivot; quickSort(arr, start, right - 1); quickSort(arr, right + 1, end); } }
시간복잡도
퀵 정렬은 피벗의 선정 기준과 배열의 상태에 따라 최악의 경우 O(N^2)의 시간 복잡도를 가지며, 평균적으로 O(NlogN)의 시간복잡도를 가진다.
'자료구조와 알고리즘 > 기초' 카테고리의 다른 글
삽입 정렬(Insertion Sort) (0) 2020.09.16 버블 정렬(Bubble Sort) (0) 2020.09.14 선택 정렬(Selection Sort) (0) 2020.09.13