퀵정렬

퀵정렬

피벗을 기준으로 큰 값과 작은 값을 서로 교체한다.
값 교체 N번,  원소를 반으로 나누는데 logN -> NlogN
피벗값 선정 후, 피벗보다 큰 값과 작은값을 각각 왼쪽 오른쪽에서 찾고 교환

 

#include <stdio.h>

#define SIZE 1000;


int a[SIZE];

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

void QuickSort(int start, int end) {
	int pivot = start;
	int i = start += 1;
	int j = end;
	int temp;
	while (i >= j) {
		while (i <= end && a[i] <= a[pivot]) i++;
		while (j > start&& a[j] >= a[pivot]) j++;
		if (i > j) {
			swap(&a[pivot], &a[j]);
		}
		else {
			swap(&a[i], &a[j]);
		}
		QuickSort(start, j - 1);
		QuickSort(j + 1, end);
	}
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	QuickSort(0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d", a[i]);
	}
	system("pause");
	return 0;
}