퀵 정렬 (Quick sort)

퀵정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 한다.

퀵 정렬이 빠른 이유

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(N㏒N)를 기대할 수 있습니다.
• 너비 X 높이 = N * ㏒N = N㏒N

퀵 정렬의 시간 복잡도

• 퀵 정렬은 평균의 경우 O(N㏒N)의 시간 복잡도를 가집니다.
• 최악의 경우 O(N²)의 시간 복잡도를 가집니다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if (start >= end):  # 원소가 1개인 경우 종료
        return
    pivot = start  # 피벗은 첫 번째 원소
    # left 는 pivot의 다음 index 부터 시작
    left = start + 1
    # right 는 last index 부터 시작
    right = end

    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때 까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때 까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1

        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]

    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

public class QuickSort {

    public void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            // 원소가 1개인 경우 종료
            return;
        }

        // 피벗은 첫 번째 원소
        int pivot = start;
        int left = start + 1;
        int right = end;

        // left의 index 보다 right의 index가 작다면 교차가 발생한 것으로 판단한다.
        while (left <= right) {

            // 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) {
                left += 1;
            }

            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) {
                right -= 1;
            }

            if (left > right) {
                // 엇갈렸다면 작은 데이터와 피벗을 교체
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            } else {
                // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }

        }

        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

		public static void main(String[] args) {
        QuickSort qs = new QuickSort();
        int[] arr = {5, 7, 9, 0, 3, 1, 6, 2, 4, 8};
        qs.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}