[정렬] 퀵 정렬

C언어

퀵 정렬

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
int value[1001] = { 0, };
 
int partition(int start, int end)
{
    int pivot = end;
    int left = start;
    int right = end;
    int temp = 0;
 
    while (left < right)
    {
        while (value[left] < value[pivot] && left < right)
        {
            // left는 pivot보다 더 큰 원소를 찾을 때 까지, 이동한다
            ++left;
        }
 
        while (value[right] > value[pivot] && left < right)
        {
            // right는 pivot보다 더 작은 원소를 찾을 때 까지, 이동한다
            --right;
        }
        
        // left와 right 교환
        if (left < right)
        {
            temp = value[left];
            value[left] = value[right];
            value[right] = temp;
        }
    }
 
    // pivot과 교환
    temp = value[right];
    value[right] = value[pivot];
    value[pivot] = temp;
 
    return right;
}
 
void quickSort(int start, int end)
{
    int pivot = 0;
 
    if (start < end)
    {
        pivot = partition(start, end);
        quickSort(start, pivot - 1);
        quickSort(pivot + 1, end);
    }
}
 
int main(void)
{
    int N = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &value[i]);
    }
 
    quickSort(0, N - 1);
 
    for (int i = 0; i < N; i++)
    {
        printf("%d\n", value[i]);
    }
 
    return 0;
}