퀵 정렬 (Quick Sort)

배열을 원하는 기준으로 재배열하는 정렬 알고리즘

 

 

 

퀵 정렬 Quick Sort

퀵 정렬은 평균적으로 매우 빠른 성능을 보이는 비교 기반 정렬 알고리즘 입니다. 

분할 정복 전략을 사용하여 피벗(Pivot)을 기준으로 범위를 나누어 가면서 정렬을 진행합니다.

배열의 한 요소를 기준이 되는 피벗으로 삼아 피벗을 기준으로 작은 것과 큰 것을 정렬합니다.

나누어진 두 부분에 또 피벗을 잡고 정렬을 하고 이 과정을 반복하여 정렬을 완성합니다. 

 

시간 복잡도 : O(n log n), 최악의 경우는 O(n^2) 입니다. 

 

퀵 정렬은 빠른 정렬 알고리즘으로 일반적인 상황일 때 속도는 다음과 같습니다.

퀵 정렬 > 힙 정렬 > 병합 정렬 

 

이 순서는 평균적인 상황이고 데이터 특성과 구현 방식에 따라 달라질 수 있습니다.

 

 

장점 

• 제자리 정렬(in-place sorting) : 원본 배열에서 정렬하므로 별도의 추가 메모리를 사용하지 않습니다. 
• 높은 효율성 : 평균적으로 O(n log n) 시간 복잡도를가지면 대부분의 경우에서 다른 정렬 알고리즘보다 빠릅니다. 

 

단점

• 최악의 경우 : 최악의 경우 O(n^2)이 됩니다. 피벗 선택이 부적절할 때 이런 상황이 됩니다. 
• 불안정한 정렬 : 안정적인 정렬 방법이 아니므로 동일한 키 값을 가진 요소들의 순서가 변경될 수 있습니다. 
• 재귀 알고리즘 : 재귀 호출을 사용하기 때문에 호출 스택이 커지면 스택 오버플로우가 발생할 수 있습니다. 이를 방지하기 위해 깊이를 제한하거나 반복적인 방식(for, while 등..)으로 구현할 수 있습니다. 

 

 

 

동작 과정

1. 배열 분할 :

피벗(Pivot)이라 불리는 한 요소를 선택합니다. 피벗 선택 방식은 알고리즘에 따라 듭니다. 피벗을 기준으로 배열을 두 부분으로 나눕니다. 왼쪽은 피벗보다 작거나 같은 요소, 오른쪽은 피벗보다 크거나 같은 요소를 둡니다. 

 

2. 재귀 

왼쪽과 오른쪽 부분에 위의 과정을 재귀적으로 수행합니다. 각 부분이 재귀적으로 정렬되면서 전체 배열이 정렬됩니다. 

 

 

예시

예시 배열 : [3, 1, 4, 2, 6, 5]

피벗을 선택하는 기준은 다양합니다. 저는 중간 요소를 피벗으로 선택하겠습니다. 

 

 

첫 번째 피벗 : index = 3, 4

피벗으로 3위치인 4를 선택했습니다. 

4를 기준으로 3,1,2인 왼쪽 부분과 5,6인 오른쪽 부분을 나눕니다. 

[3, 1, 2] 4 [6, 5]

 

 

왼쪽 배열 [3, 1, 2]

[3, 1, 2] 에서 중간에 위치한 1을 피벗으로 선택합니다.

1을 기준으로 왼쪽 부분, 오른쪽 부분을 나눕니다. 

결과 배열 : 1, [2, 3]

 

왼쪽인 1인 부분은 배열의 크기가 1이므로 완전히 정렬되었습니다. 

 

 

오른쪽 배열 [2, 3]

1은 정렬되었으므로 2,3을 비교합니다. 

2를 피벗으로 둡니다. 

결과 배열 : [2,3]

 

더 이상 나눌 수 없는 1의 자리까지 왔으므로 왼쪽 부분은 정렬이 완료되었습니다.

[1, 2, 3, 4] [5, 6]

 

 

오른쪽 배열 [6,5]

오른쪽인 [6, 5] 부분을 정렬합니다.

 

피벗은 5로 선택합니다.

결과 배열 : 5,[6] 

 

더 이상 나눌 수 없는 1의 자리까지 왔으므로 오른쪽 부분은 정렬이 완료되었습니다. 

 

 

정렬 결과 

결과적으로 모든 배열이 정렬이 완성됩니다.

정렬 배열 : [1, 2, 3, 4, 5, 6]

 

 

 

 

Java 코드

/*
퀵 소트

참고 영상 : https://www.youtube.com/watch?v=7BDzle2n47c
 */
public class QuickSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    quickSort(array);
    printArray(array);
  }

  // 퀵 정렬 시작
  public static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
  }

  // 재귀 수행(pivot을 중심으로 왼쪽 작은 것, 오른쪽 큰 것으로 한다)
  public static void quickSort(int[] array, int start, int end) {
    int part2 = partition(array, start, end); // 오른쪽의 첫 번째 인덱스를 받아옴

    // 처음 위치가 오른쪽 첫 번째 인덱스 바로 다음 칸이면 왼쪽의 크기가 1이라는 뜻
    // part2 - 1 이 2 이상일 때는 왼쪽의 크기가 2 이상이라는 뜻으로 정렬을 진행한다.
    if(start < part2 - 1) {
      quickSort(array, start, part2 - 1);
    }
    // 오른쪽 부분의 첫 번째 시작점이 end이면 오른쪽 크기가 1이라는 뜻
    // part2 < end 는 오른쪽 크기가 2 이상이란 뜻으로 정렬을 진행한다.
    if(part2 < end) {
      quickSort(array, part2, end);
    }
  }

  // 배열을 나누는 부분
  public static int partition(int[] array, int start, int end) {
    // 여기서 pivot은 중간 지점으로 설정
    int pivot = array[(start + end) / 2];

    // 반복문을 통해 pivot을 중심으로 왼쪽은 작은 값, 오른쪽은 큰 값이 오게 된다.
    while(start <= end) {
      // 왼쪽에서 pivot 보다 큰 값을 찾음
      while(array[start] < pivot) start++;

      // 오른쪽에서 pivot 보다 작은 값을 찾음
      while(array[end] > pivot) end--;

      // 두 개의 인덱스를 교환하고 탐색을 계속한다.
      if(start <= end) {
        swap(array, start, end);
        start++;
        end--;
      }
    }
    // while문을 반복하면 start에는 오른쪽 부분의 첫 번째 인덱스가 저장된다.
    return start;
  }

  // 배열의 2개의 위치의 값을 바꿈
  public static void swap(int[] array, int start, int end) {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
  }

  // 배열 출력
  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

 

마무리

이번에는 퀵 정렬에 대해 정리했습니다.

다음에는 병합 정렬에 대해 정리해 보겠습니다.

감사합니다.