quick sort

quick sort 중 피봇이 맨 오른쪽에 위치한 quick sort를 알아보려고 한다.

 

우선 quick sort에서 가장 중요한 피벗이란 하나의 기준점을 말한다. 

이 피벗을 중심으로 피벗의 앞에는 피벗보다 작은 원소들을, 뒤에는 피벗보다 큰 원소들을 나열하여 피벗의 위치를 확정시켜 나아가다. 결국엔 모든 원소가 정렬되는 알고리즘이 quick sort알고리즘이다.

 

 

 

 

출처: Quicksort in JavaScript (morioh.com)

 

 위의 사진도 마찬가지로 피벗을 맨 오른쪽 원소로 잡은다음 quick sort를 진행한 결과이다. 

quick sort는 운이 좋으면 O(nlogn)의 시간복잡도를 가지지만 운이 좋지 못하면 O(n^2)의 시간 복잡도를 가진다.

또한 quick sort는 피벗의 위치에 따라 시간복잡도의 차이가 나는데 피벗을 맨 오른쪽에 위치한 원소로 잡는 방식 말고도 가운데 또는 맨 왼쪽원소로 잡는 등 다양한 방식으로 피벗을 구하는 알고리즘들이 있다. 

 

 

 

Code

#include <stdio.h>
#define MAX 10

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; 

    for (int j = low; j < high; j++) { // 피벗 전까지 반복
        if (arr[j] < pivot) { // 만약 원소가 피벗보다 작은가?
            swap(&arr[i++], &arr[j]); // 시작 원소와 비교원소를 교환 후 i증가
        }
    }
    swap(&arr[i], &arr[high]); // 피벗보다 작은 원소들은 피벗 앞에 위치하게 된다.
    return i; // 피벗의 index 반환
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // pi = 피벗의 인덱스
        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[] = { 123, 35, 415, 11, 56, 9, 0, 523, 1000, 10 };

    printf("before :  ");
    printArray(arr, MAX);

    quickSort(arr, 0, MAX -1);

    printf("after : ");
    printArray(arr, MAX);

    return 0;
}

 

 

 

 

 

Reference

• Quicksort in JavaScript (morioh.com)
• 퀵 정렬(Quick Sort) (tistory.com)