[알고리즘] 퀵소트(QuickSort) 구현 (C)

 

수, 문자열 등 정렬이 필요한 상황에 퀵소트를 라이브러리 없이 구현하기 위함

 

정렬 조건 자체가 많더라도, while문 안에서 모두 해결이 가능하다.

 

 

#include <stdio.h>
 
int arr[] = { 1, 10, 6, 9, 8, 2 };
 
void quickSort(int *, int start, int end);
 
int main(void)
{
    int size = sizeof(arr) / 4;
 
    printf("Before : ");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    quickSort(arr, 0, size - 1);
 
    printf("After : ");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    return 0;
}
 
void quickSort(int *arr, int start, int end) {
 
    if (start >= end) return;
 
    if (start < end) {
 
        int i = start - 1;
        int j = end + 1;
        int pivot = arr[(start + end) / 2];
 
        while (i < j) {
            while (arr[++i] < pivot) {}
            while (arr[--j] > pivot) {}
 
            if (i >= j) break;
 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
 
        quickSort(arr, start, i - 1);
        quickSort(arr, j + 1, end);
    }
 
}