[알고리즘] Quick Sort 정리 - C

Quick Sort (빠른 정렬)

Quick Sort에 대해 공부를 해보았다.
Quick Sort는 정렬 알고리즘 중 가장 유명한 알고리즘 중 하나라고 한다.
그러하여 여러 변형된 버전들이 있다 그 중 나는 가장 기본적인 버전을 구현해 보았다.

구현 방식

내가 구현한 Quick Sort는 대개의 경우와는 다르게 가장 왼쪽을 기준으로 잡는 코드를 구현하였다.
아래는 내가 구현한 Quick Sort의 과정이다.

#include <stdio.h>
// -- Quick Sort --
// 1. 분할정복 (Divide & Conquer)
// 2. 재귀함수 (Recursive Function)
//
// - Function -
// 1. 교환 (Swap)
// 2. 분할 (Divide)
// 3. 정복 (Conquer)

// 교환 (Swap)
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// 분할 (Divide)
// 해당 함수에서는 l(Left)를 기준으로 삼는다.
int partition(int arr[], int l, int r) {
    // 기준
    int pivot = arr[l];
    
    // 비교위치 (현위치의 값보다 큰 값을 가리키고 있음)
    int i = l;

    // 기준을 제외한 부분을 모두 탐색    
    for(int j=l+1; j<=r; j++) {
        
        // 만약 기준보다 현위치 값이 낮을 경우
        if(arr[j] <= pivot) {
            
            // 비교위치를 1올림
            i++;
            
            // 비교위치와 현위치를 교환
            swap(&arr[i], &arr[j]);
        }
    }
    
    // 비교위치와 기준위치 교환
    swap(&arr[i], &arr[l]);
    
    // 기준의 위치 반환
    return i;
}

// 정복 (Conquer)
void quickSort(int arr[], int l, int r) {
    // 시작 위치가 끝 위치 보다 작을 경우 진입
    if(l < r) {
        // 기준 (pivot) 정하기
        int p = partition(arr, l, r);
        
        // 왼쪽 (Left) 구역 정복
        quickSort(arr, l, p-1);
        
        // 오른쪽 (Right) 구역 정복
        quickSort(arr, p+1, r);
    }
}


int main() {
    int arr[] = {5, 1, 3, 2, 4};
    
    quickSort(arr, 0, 4);
    
    for(int i=0; i<5; i++) printf("%d ", arr[i]);

    return 0;
}