Quick Sort 구현

퀵소트는 아래 두가지 연산이 중요

• Pivot
• Partition

두가지 구현 방법

1

브라이언 커니핸(무려 K&R의 K에 해당하는 사람)이 쓴 책 프로그래밍 수련법책에서 참고한 코드인데, 구현이 매우 간단하고 좋다. 비교 대상의 값을 맨 앞으로 보내고 풀이하는 방법.

#include <stdio.h>
#define ARR_SIZE30
int arr[ARR_SIZE] = {23, 46, 3, 19, 7, 2, 770, 450, 50, 78, 
			1230, 1460, 130, 150, 270, 320, 377, 345, 35, 31,
			230, 460, 30, 50, 70, 20, 77, 45, 5, 1};
void swap(int arr[], int a, int b);

void quick_sort(int arr[], int n)
{
	int pivot, i;
	
	if (n <= 1) /* base case */
		return;
	swap(arr, 0, (n/2)); /* move standard value(middle) to 0 idx*/
	pivot = 0; 
	for (i = 1; i < n; i++)
		if (arr[i] < arr[0]) /* if arr[i] is less than standard value */
			swap(arr, ++pivot, i); /* put arr[i] on the left side of pivot */
	swap(arr, 0, pivot); /* recover standard value */
	quick_sort(arr, pivot); /* recursive call left side */
	quick_sort(arr + pivot + 1, n - pivot -1); /* recursive call right side */
}

void print_arr(int arr[]);

int main(int argc, char *argv[])
{
	print_arr(arr);
	quick_sort(arr, ARR_SIZE);
	print_arr(arr);
	return 0;
}

2

pivot기준으로 양단의 값을 끝에서 가운데로 좁히면서 swap하는 방법.

#include <stdio.h>
void swap(int arr[], int a, int b);
int partition(int arr[], int left, int right);

int array[] = {3,4,1,5,43,12,321,35,6,876,100,83,923,38,91,611,892,999,37};

void quick_sort(int arr[], int left, int right)
{
        if (left < right) {
                int pivot = partition(arr, left, right);
                quick_sort(arr, left, pivot - 1);
                quick_sort(arr, pivot + 1, right);
        }
}

int partition(int arr[], int left, int right)
{
        int pivot = arr[(left + right) / 2];
        while (left <= right) {
                while (arr[left] < pivot) left++;
                while (arr[right] > pivot) right--;
                if (left <= right)
                        swap(arr, left++, right--);
        }
        return left;
}

void swap(int arr[], int a, int b)
{
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
}


void print_arr(int arr[])
{
	for (int i = 0; i < ARR_SIZE; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main(int argc, char *argv[])
{
        int sizea = sizeof(array) / sizeof(int);

        printf("before\n");
        for (int i = 0; i < sizea; i++)
                printf("%d ", array[i]);

        quick_sort(array, 0, sizea - 1);

        printf("\nafter\n");
        for (int i = 0; i < sizea; i++)
                printf("%d ", array[i]);
        printf("\n");
        return 0;
}