자료구조 - Sort (Quick Sort)

Quick Sort

정의 : 분할정복 알고리즘으로 부분적으로 나누어가면서 정렬하는 방법.

• 시간 복잡도
  최악: O(n^2)
  평균: O(n*logn)

• java에서 Arrays.sort()로 사용한다.

Quick Sort 실행 방식

1. 배열을 두 부분으로 나눈다.
   i) 배열 내 기준 요소보다 작으면 앞부분 배열에 위치, 크면 뒷부분 배열에 위치한다.
2. 각 분할된 부분을 재귀적으로 정렬한다.

package javastudy;

public class quickSort {
  public static void qs(int a[], int low, int high) {
    if (low < high) {
      int s = partition(a, low, high); // 기준 pivot
      qs(a, low, s - 1); // 왼쪽 배열
      qs(a, s + 1, high); // 오른쪽 배열
    }
  }

  public static int partition(int a[], int low, int high) {
    int pivot = a[low]; // 피벗을 배열의 첫 번째 요소로 설정
    int i = low + 1;
    int j = high;

    while (i <= j) {
      while (i <= high && a[i] <= pivot) {
        i++;
      }
      while (j >= low && a[j] > pivot) {
        j--;
      }
      if (i < j) { // i가 j보다 작을 때만 교환
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
      }
    }
    // 피벗을 올바른 위치에 배치
    a[low] = a[j];
    a[j] = pivot;

    return j; // 피벗의 최종 위치 반환
  }

  public static void printArray(int a[]) {
    for (int num : a) {
      System.out.print(num + " ");
    }
    System.out.println(); // 배열 출력 후 줄바꿈
  }

  public static void main(String[] args) {
    int a[] = {8, 5, 6, 2, 4};
    printArray(a);
    qs(a, 0, a.length - 1); // 배열의 크기를 사용하여 인덱스 설정
    printArray(a);
  }
}