[자료구조] C언어 퀵 정렬 quick sort

Quick Sort(퀵 정렬)

퀵 정렬은 평균적으로 O(nlogn)번의 비교를 수행하며 최악의 경우에 O(n^2)의 비교를 수행합니다.

퀵 정렬은 다음과 같은 방식으로 진행

1. 주어진 데이터 목록에서 임의의 원소를 고른다. 이 원소가 Pivot이다.

(Pivot을 어떻게 정하느냐의 따라 비교 횟수가 달라진다)

2. pivot을 가장 왼쪽으로 이동시킨 뒤 Left는 Pivot값 보다 큰 값을 찾을때까지 오른쪽으로 이동하고 Right는 Pivot값 보다 작은 값을 찾을때까지 왼쪽으로 이동한다.

3. 찾으면 교환한다.

4. Left가 Right를 만나거나 지나가게 되면 Pivot과 교환한다.

5. 그렇게 되면 Pivot을 기준으로 왼쪽은 작은데이터 오른쪽은 큰데이터로 이루어진다.

6. 이렇게 왼쪽부분과 오른쪽부분을 1~5의 과정을 반복하여 정렬한다.

C Code (내림차순)

void swap(int* a,int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
void quick_sort(int* array, int start, int end){
    if(start>=end) return;
    int mid = (start+end)/2;
    int pivot = array[mid];
    
    swap(&array[start],&array[mid]);
    
    int left = start+1, right = end;
    while(1){
        while(array[left]<=pivot){left++;}
        while(array[right]>pivot){right--;}
        if(left>right) break;
        swap(&array[left],&array[right]);
    }
    swap(&array[start],&array[right]);
    
    quick_sort(array,start,right-1);
    quick_sort(array,right+1,end);
}

code 16,17 : while문을 변경하면 오름차순 내림차순이 변한다.

오름차순은 code 16,17의 <= , > 를 >= , <로 바꾸면 된다.

+)

<stdlib.h>에서 qsort를 제공합니다.

비교함수 코드 및 사용 코드

int compare(const void *arg1, const void *arg2){
    if (*(int*)arg1 > *(int*)arg2) return -1;
    else if (*(int*)arg1 == *(int*)arg2) return 0;
    else return 1;
}
 
qsort((void*)A, (size_t)a, sizeof(int), compare);
 
 

qsort 사용하기

qsort(void* base,size_t nel,size_t width,int (*compare));

base : 정렬할 배열의 첫번째 포인터

nel : 배열의 갯수

width : 배열 하나의 크기

(*compare) : 비교함수