퀵 정렬

퀵 정렬

- 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법

- 값을 서로 교체하는 데에 n번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logn번이 소요되므로 평균적으로 0(nlogn)의 시간 복잡도를 가짐

- 원소를 절반씩 나눌 때 logn의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리임

- 이러한 완전 이진 트리 형태는 흔히 컴퓨터 공학에서 가장 선호하는 이상적인 형태

- 편향된 분할이 발생할 때 연산의 양이 0(n2) 임

- 실제로 정렬을 함에 있어서는 퀵 정렬을 직접 구현하지 않음

- C++의 Algorithm라이브러리를 사용

- Algorithm 라이브러리의 sort() 함수는 퀵 정렬을 기반으로 하되 0(nlogn)을 보장함

 

* 배열 선언

#define _CRT_SECUCRE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define SIZE 1000

int a[SIZE];

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

 

* 퀵 정렬 구현하기

void quickSort(int start, int end) {
    if (start >= end) return;
    int key = start, i = start + 1, j = end, temp;
    while (i <= j) { // 엇갈릴 때까지 반복
        while (i <= end && a[i] <= a[key]) i++;
        while (j > start && a[j] >= a[key]) j--;
        if (i > j) swap(&a[key], &a[j]);
        else swap(&a[i], &a[j]);
    }
    quickSort(start, j - 1);
    quickSort(j + i, end);
}

 

* 퀵 정렬 사용해보기

void quickSort(int start, int end) {
    if (start >= end) return;
    int key = start, i = start + 1, j = end, temp;
    while (i <= j) { // 엇갈릴 때까지 반복
        while (i <= end && a[i] <= a[key]) i++;
        while (j > start && a[j] >= a[key]) j--;
        if (i > j) swap(&a[key], &a[j]);
        else swap(&a[i], &a[j]);
    }
    quickSort(start, j - 1);
    quickSort(j + i, end);
}

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) printf("%d", a[i]);
    system("pause");
    return 0;
}