[정렬-빠른 정렬]

[정렬-퀵정렬]

2024-07-12

Quick Sort는 분할 정복 전략을 기반으로 한 효율적인 정렬 알고리즘입니다. 이 정렬 알고리즘의 핵심 아이디어는 벤치마크 요소를 선택하고 배열을 두 부분으로 분할하여 왼쪽 요소가 벤치마크 요소보다 작거나 같고 오른쪽 요소가 벤치마크 요소보다 크거나 같도록 하는 것입니다. 벤치마크 요소와 동일한 다음 두 부분에 재귀적으로 빠른 정렬을 적용합니다.

알고리즘 단계:

기본 요소 선택 : 배열에서 피벗으로 요소를 선택합니다. 일반적으로 첫 번째 요소, 마지막 요소 또는 임의의 요소가 기본으로 선택됩니다.
분할 : 기본 요소보다 작은 요소는 기본 요소의 왼쪽에, 기본 요소보다 큰 요소는 오른쪽에 있도록 배열을 재배열합니다. 동시에 기본 요소는 최종 정렬 위치에 있습니다.
재귀 정렬: 참조 요소의 왼쪽과 오른쪽에 있는 하위 배열을 재귀적으로 빠르게 정렬합니다.

구현 단계:

C 언어에서 빠른 정렬을 구현하는 코드는 다음과 같습니다.

#include <stdio.h>

// 函数：交换数组中两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 函数：将数组分区，并返回基准元素的位置（索引）
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 初始化分区索引，比基准元素小的元素会放在左边

    for (int j = low; j < high; j++) {
        // 如果当前元素小于或等于基准元素，则将它交换到分区的左边
        if (arr[j] <= pivot) {
            i++;  // 移动分区索引
            swap(&arr[i], &arr[j]);
        }
    }

    // 最后将基准元素交换到正确的位置
    swap(&arr[i + 1], &arr[high]);
    return i + 1;  // 返回基准元素的位置
}

// 函数：实现快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 对数组进行分区
        int pi = partition(arr, low, high);

        // 对基准元素左边和右边的子数组进行递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 函数：打印数组元素
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
}

// 主函数：测试快速排序的实现
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组: n");
    printArray(arr, n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

코드 분석:

스왑 기능: 배열의 두 요소 값을 교환하는 데 사용됩니다.
파티션 기능: 배열의 마지막 요소를 기본으로 선택하고 배열을 두 부분으로 나눈 후 기본 요소의 최종 위치 인덱스를 반환합니다.
퀵정렬 기능 : 빠른 정렬을 위해 재귀 알고리즘을 구현합니다. 각 재귀에서는 먼저 분할 함수를 사용하여 배열을 분할한 다음 분할된 두 부분을 재귀적으로 정렬합니다.
printArray 함수: 정렬 결과를 쉽게 볼 수 있도록 배열 요소를 인쇄하는 데 사용됩니다.
주요 기능: 빠른 정렬 구현을 테스트하고 정렬 전후의 배열을 인쇄합니다.

시간 복잡도:

퀵 정렬의 시간 복잡도는 주로 파티션 작업의 시간 복잡도와 재귀 호출 횟수에 따라 달라집니다. 퀵정렬의 시간 복잡도는 최악의 경우 O(n^2)이지만, 평균적인 경우에는 O(n log n)이므로 효율적인 정렬 알고리즘입니다.

요약하다:

퀵 정렬은 분할 정복 전략과 분할 연산을 통해 효율적인 정렬을 구현합니다. 추가 저장 공간이 필요하지 않으며(재귀 호출을 위한 스택 공간 제외) 평균적인 상황에서 좋은 성능을 발휘합니다. 따라서 빠른 정렬은 실제 응용 프로그램에서 일반적으로 사용되는 정렬 알고리즘 중 하나이며 특히 대규모 데이터 세트의 정렬 작업에 적합합니다.

기술나눔