Quicksort

퀵 정렬 알고리즘

퀵 정렬이란?

• 퀵 정렬은 분할 정복 알고리즘이다.
• 이름 그대로 다른 정렬 알고리즘에 비해 빠른 속도가 장점이다.
• 불안정한 정렬이라는 특징이 있어서 값이 동일한 항목들의 순서를 보장하지 않는다.
• 배열에서 피벗pivot 요소를 선택하고 다른 요소들이 피벗보다 큰지 작은지에 따라 두 개의 하위 배열로 나눈다. 피벗을 어떤 기준으로 선택하느냐에 따라 성능이 달라진다.

퀵 정렬 알고리즘의 흐름

분할 Divide: 하나의 요소를 피벗으로 선택하고, 이를 기준으로 작은 요소들은 피벗의 왼쪽, 큰 요소들은 피벗의 오른쪽으로 이동시킨다.
정복 Conquer: 피벗을 기준으로 배열을 두 부분으로 나누고, 각 부분을 재귀적으로 반복한다.
결합 Combine: 부분 배열들이 정렬되면, 결합하여 전체 배열을 완성한다.

시간복잡도

Java 예제

public void quickSort(int[] arr, int left, int right) {
    // base condition
    if (left >= right) {
        return;
    }
    int pivot = arr[right];
    
    int sortedIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap(arr, i, sortedIndex);
            sortedIndex++;
        }
    }
    swap(arr, sortedIndex, right);
    quickSort(arr, left, sortedIndex - 1);
    quickSort(arr, sortedIndex + 1, right);
}

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

참고

Quicksort
퀵 정렬
What is the space and time complexity of a quick sort algorithm?

수정이 필요한 부분은 댓글로 피드백 부탁드립니다!