빠른 정렬(Quick Sort)

빠른 정렬(Quick Sort)

---

빠른 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 기법을 기반으로 하는 정렬 알고리즘입니다. 빠른 정렬은 합병 정렬과 비슷하지만 빠른 정렬은 배열을 분할하는 방식이 다릅니다. 입력 배열에서 하나의 기준값(pivot)을 선택하고 기준값보다 작으면 왼쪽 배열, 크면 오른쪽 배열로 분할한 뒤 재귀적으로 정렬합니다.

 

빠른 정렬의 동작 원리

1. 기준값(Pivot) 선택 : 배열에서 원소 하나를 기준값으로 선택합니다. 일반적으로 배열의 첫 번째, 중간, 마지막 원소 값을 선택합니다.
2. 분할(Divide) : 기준값보다 작은 값은 왼쪽 배열, 큰 값은 오른쪽 배열에 배치합니다.
3. 정복(Conquer) : 왼쪽과 오른쪽 배열을 재귀적으로 정렬합니다.

빠른 정렬의 특징

시간 복잡도

• 평균 : O(n log n)
• 최악 : O(N^2)

공간 복잡도

• O(log n)

그 외

추가 메모리 사용 없이 배열 내부에서 정렬할 수 있지만 원소 간 순서가 유지되지 않을 수 있습니다.

 

빠른 정렬의 구현(Java 구현)

class Quick {
    public void quicksort(int[] S, int low, int high) {
        if (low < high) {
            // 파티션 인덱스를 구한다
            int pi = partition(S, low, high);

            // 파티션을 기준으로 왼쪽과 오른쪽 부분을 재귀적으로 정렬
            quicksort(S, low, pi - 1);  // 왼쪽 부분
            quicksort(S, pi + 1, high); // 오른쪽 부분
        }
    }
    public int partition(int[] S, int low, int high) {
        // 피벗을 배열의 마지막 원소로 선택
        int pivot = S[high];
        int i = low - 1; // 작은 원소들의 인덱스를 추적

        // low부터 high-1까지 순회하며, 피벗보다 작은 값을 왼쪽으로 모은다
        for (int j = low; j < high; j++) {
            if (S[j] < pivot) {
                i++;
                // i와 j의 값을 교환
                swap(S, i, j);
            }
        }

        // 마지막으로 피벗을 올바른 위치에 배치
        swap(S, i + 1, high);
        return i + 1;  // 피벗이 위치한 인덱스를 반환
    }

    public void swap(int[] S, int i, int j) {
        int temp = S[i];
        S[i] = S[j];
        S[j] = temp;
    }
}
public class QuickSort {
    public static void main(String[] args) {
        int[] S = new int[] { 10, 12, 20, 27, 13, 9, 22, 25 };
        Quick quick = new Quick();
        quick.quicksort(S, 0, S.length - 1);
        System.out.print("빠른 정렬 : ");
        for(int num : S) {
            System.out.print(num + " ");
        }
    }
}

 

빠른 정렬의 장단점

빠른 정렬의 장점

이름이 빠른 정렬이라는 것에서 알 수 있듯이 대부분의 병합 정렬보다 빠르게 동작하면서 추가 메모리 사용이 거의 없습니다. 그리고 기준값 선택 방법에 따라 알고리즘을 최적화할 수 있습니다.

 

빠른 정렬의 단점

데이터가 이미 정렬되어 있는 경우 오히려 시간 복잡도가 O(N^2)이 되면서 비효율적이 되며 원소 간의 순서가 유지되지 않습니다.