[10]

1. 퀵 정렬

가장 빠른 정렬 알고리즘

피벗 값을 기준으로 배열을 두 그룹으로 나누기

#include<stdio.h>
#define swap(type, x, y) do { type t=x; x=y; y=t;} while(0)
void partition(int a[], int n){
        int i;
        int pl=0; // 왼쪽 커서
        int pr=n-1; // 오른쪽 커서
        int x = a[n/2]; // 피벗 값
        do{
                while(a[pl] < x) pl++;
                while(a[pr] > x) pl--;
                if(pl<=pr){
                        swap(int, a[pl], a[pr]);
                        pl++
                        pr--;
                }
        }while(pl<=pr);
}

퀵 정렬

#include<stdio.h>
#define swap(type, x, y) do { type t=x; x=y; y=t;} while(0)
void quick(int a[], int left, int right){ // left와 right는 각각 첫번째값과 끝값
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];
        do{
                while(a[pl]<x) pl++;
                while(a[pr]>x) pr--;
                if(pl<=pr){
                        swap(int, a[pl], a[pr]);
                        pl++;
                        pr--;
                }
        }while(pl<=pr);
        if(left<pr) quick(a, left, pr);
        if(pl<right) quick(a, pl, right);
}