quick sort - c

퀵소트를 c로 구현해봤다. 퀵소트는 처음부터 재귀호출을 이용해서 구현했다.

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

void print_array(int *x, int n);

int* scaffolding(int n);

void quicksort(int *x, int n);

void swap(int *, int *);

int main() {

int *x, n, i;

printf("배열 크기 : ");

scanf("%d", &n);

x = scaffolding(n);

print_array(x, n);

quicksort(x, n);

print_array(x, n);

return 0;

}

void quicksort(int *x, int n) {

if(n <= 1)

return;

int i, m = 0;

for(i = 1; i < n ; ++i) {

if(x[0] > x[i]) {

swap(&x[++m], &x[i]);

}

}

swap(&x[m], &x[0]);

quicksort(x, m);

quicksort(x+m+1, n-m-1);

}

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = temp;

}

void print_array(int *x, int n) {

int i;

for(i = 0; i < n; ++i)

printf("%d ", x[i]);

printf("\n");

}

int* scaffolding(int n) {

srand((unsigned) time(NULL));

int *x, i;

x = (int *)malloc(n * sizeof(int));

for(i = 0; i < n; ++i)

x[i] = rand() % n;

return x;

}

밑의 함수는 정렬하는 부분만 다른 알고리즘으로 풀어봤다.

void quicksort(int *x, int n) {

if(n <= 1)

return;

int l = 0, u = n;

while(1) {

do {++l;} while(x[0] > x[l] && l < n);

do {--u;} while(x[0] <= x[u] && u > 0);

if(u < l)

break;

swap(&x[l], &x[u]);

}

swap(&x[0], &x[u]);

quicksort(x, u);

quicksort(x+u+1, n-u-1);

}