[퀵 정렬] 배열을 이용한 퀵 정렬 구현

-

-

-

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int findPivot(int* x, int l, int r) {

	if (r - l <= 1)
		return l;

	srand((unsigned)time(NULL));
	int pivot = (rand() % (r - l)) + l;

	return pivot;
}

void swap(int *a, int *b) {
	int tmp;
	tmp = a;
	a = b;
	b = tmp;
}

int inPlacePartition(int* x, int l, int r, int k) {
	int p;
	int tmp, left = l+1, right = r;

	p = x[k];
	tmp = x[l];
	x[l] = x[k];
	x[k] = tmp;


	while (left<=right) {
		if (x[left] < p) {
			left++;
			continue;
		}

		if (x[right] >= p) {
			right--;
			continue;
		}

		if (left >= right)
			break;

		tmp = x[left];
		x[left] = x[right];
		x[right] = tmp;
	}

	tmp = x[left - 1];
	x[left - 1] = x[l];
	x[l] = tmp;

	return right;
}

void inPlaceQuickSort(int *x, int l, int r) {
	int k, a, b;
	int t;
	if (l >= r)
		return;

	k = findPivot(x, l, r);
	t = b = inPlacePartition(x, l, r, k);

	while (1) {
		if (x[t] != x[b]) {
			a = t + 1;
			break;
		}
		t--;
	}
	inPlaceQuickSort(x, l, a - 1);
	inPlaceQuickSort(x, b + 1, r);

	return;
}

void print(int* x, int n) {
	for (int i = 0; i < n; i++) {
		printf(" %d", x[i]);
	}
}

int main() {
	int n, e;//배열 크기, 원소
	scanf("%d", &n);

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

	for (int i = 0; i < n; i++) {
		scanf("%d", &x[i]);
	}

	inPlaceQuickSort(x, 0, n - 1);
	print(x, n);

	free(x);

	return 0;
}