[알고리즘] 퀵정렬

퀵정렬이란?

퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다.

퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다.

퀵정렬의 전체적인 정렬 과정

퀵정렬은 임의의 pivot 값을 기준으로
pivot 의 좌측에는 pivot 보다 작은값을 두고
우측에는 pivot 보다 큰 값을 두는 방식으로 정렬을 진행한다.

전체적인 정렬 과정은 다음과 같다.

1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot) 이라고 하자.

2. pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 원소를, pivot의 오른쪽에는 pivot보다 큰 원소를 배치한다.

3. pivot을 기준으로 분할된 왼쪽 리스트와 오른쪽 리스트에 대해 다시 1,2의 과정을 반복한다.

4. 이렇게 순환 과정을 통해 분할된 각 리스트의 크기가 0이나 1이 되면 수행을 종료한다.

퀵정렬의 자세한 정렬과정

이를 그림과 함께 좀 더 자세한 과정으로 살펴보자.

1. 피봇을 선택한다.

2. left는 왼쪽에서 오른쪽으로 가면서 피봇보다 작은 수를 찾는다.

3. right는 오른쪽에서 왼쪽으로 가면서 피봇보다 큰 수를 찾는다.

4. 찾은 지점에서 left와 right를 교환한다.

5. 위의 2,3,4과정 left와 right가 교차할 때 까지 반복한다.

6. left와 right가 교차하면 피봇(pivot)과 right를 교환한다.

7. 이렇게 되면 피봇의 왼쪽에는 피봇보다 작은수가, 피봇의 오른쪽에는 피봇보다 큰 수가 위치한다.

8. 피봇을 기준으로 왼쪽과 오른쪽 리스트 두개로 나눠 위의 과정을 반복 수행한다.

9. 이렇게 순환 과정을 통해 분할된 리스트의 크기가 0이나 1이 되면 수행을 종료한다.

퀵 정렬의 구현 코드(오름차순)

public class QuickSort {

  public static void main(String[] args) {
    int[] arr = { 3, 1, 5, 6, 20, 10, 7, 11, 15, 9 };
    quickSort(arr);
  }

  public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

퀵 정렬의 장점 및 단점

• 장점
  • 속도가 빠르다 (평균 속도가 O(NlogN) 이며 O(NlogN)의 속도를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
  • 추가 메모리 공간이 필요하지 않다 (O(logN) 만큼의 메모리를 필요로 한다.)
• 단점
  • 최악의 경우 시간 복잡도는 O($N^2$) 이다.

출처

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/QuickSort.md
https://hongcoding.tistory.com/185