[알고리즘] 퀵정렬(Quick Sort)

퀵정렬(Quick Sort)은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘이다. 퀵정렬은 재귀적으로 배열을 정렬하며, 데이터가 큰 경우에도 매우 빠른 성능을 자랑한다.

퀵정렬은 추가적인 메모리 공간을 많이 사용하지 않는 제자리(in-place) 정렬 알고리즘이다.

퀵정렬의 시간 복잡도

평균적으로 O(n log n)의 시간 복잡도를 가지며, 특히 큰 데이터셋에서 효율적이다.
이미 정렬된 배열이나 모든 요소가 동일한 경우, 비효율적인 피벗 선택으로 인해 시간 복잡도가 O(n²)까지 증가할 수 있다.

퀵정렬의 원리

1. 배열에서 하나의 요소를 선택한다. 이 요소를 피벗이라고 한다. 피벗은 배열의 중간에 위치한 값이나 임의로 선택된 값일 수 있다.

2. 배열을 피벗을 기준으로 두 부분으로 나눈다. 피벗보다 작은 값들은 피벗의 왼쪽에, 피벗보다 큰 값들은 피벗의 오른쪽에 위치하게 한다. 이 과정을 통해 피벗은 최종적으로 정렬된 위치에 자리 잡게 된다.

3. 피벗을 기준으로 나뉜 두 개의 서브 배열에 대해 재귀적으로 퀵정렬을 적용한다. 이 과정은 배열의 크기가 1이 될 때까지 반복되며, 재귀적 정렬(Recursion)이라고 한다.

4.모든 재귀 호출이 완료되면 배열이 완전히 정렬된 상태가 된다.

자바와 자바스크립트로 구현해보자.

퀵정렬 - 자바(Java)

public class QuickSort {
    
    // 배열을 정렬하는 메인 함수
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            
            // 분할된 두 부분을 재귀적으로 정렬
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }
    
    // 피벗을 기준으로 배열을 분할하는 함수
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // 마지막 요소를 피벗으로 선택
        int i = (low - 1);  // 작은 요소의 인덱스
        
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                
                // 작은 요소를 왼쪽으로 이동
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        
        // 피벗을 올바른 위치로 이동
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        
        return i + 1;
    }

    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;
        
        quickSort(array, 0, n - 1);
        
        System.out.println("정렬된 배열:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

퀵정렬 - 자바스크립트(JavaScript)

function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const pivot = array[array.length - 1];  // 마지막 요소를 피벗으로 선택
    const left = [];
    const right = [];

    // 피벗을 기준으로 배열을 분할
    for (let i = 0; i < array.length - 1; i++) {
        if (array[i] < pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }

    // 분할된 두 부분에 대해 재귀적으로 퀵정렬 적용
    return [...quickSort(left), pivot, ...quickSort(right)];
}

const array = [10, 7, 8, 9, 1, 5];
const sortedArray = quickSort(array);

console.log("정렬된 배열:", sortedArray);