[Sort] 퀵 정렬 (Quick Sort)

소개

• Pivot 기준으로 정렬을 진행한다.
• 앞서 배운 정렬들에 비해 빠른 속도를 가진다.
• 시간 복잡도는 평균적으로 O(nlogn) 을 가진다. 하지만 최악일 경우엔 O(n2) 을 가진다.

 

동작원리

• 배열 안에 기준이 될 원소를 선택 → Pivot
• Pivot을 기준으로 pivot 보다 작은 원소는 모두 왼쪽으로 옮기고 큰 원소는 모두 오른쪽으로 옮겨 분할 과정을 거친다.
• pivot 을 제외한 왼쪽 배열과 오른쪽 배열의 리스트를 정렬한다.
  • 분할된 배열을 가지고 위의 순서를 더이상 분할이 안될 때 까지 반복한다.

 

구현코드

public static void sort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int i = left;
    int j = right;

    int pivot = arr[(left + right) / 2];

    while (i < j) {
        while (arr[i] < pivot) {
            i++;
        }

        while (arr[j] > pivot) {
            j--;
        }

        if (i >= j) {
            break;
        }

        if (arr[i] == pivot && arr[j] == pivot) {
            i++;
            continue;
        }

		swap(arr, i, j);
    }

	sort(arr, left, i - 1);
	sort(arr, i + 1, right);
}

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