퀵소트구현

2018. 7. 13. 17:10

안녕하세요 오늘은 퀵소트에 대해 학습해보겠습니다. C언어에서 퀵소트는 라이브러리로 제공되기때문에 이용하여 정렬을 빠른 시간에 할 수 있습니다. 하지만 라이브러리의 제약이 있다면 직접 구현해야 하는경우도 발생합니다. 그리고 퀵소트를 사용하기전에 어떤 원리로 작동하는지 알면 좋겠죠?




퀵소트의 특징은 아래와 같습니다.




주어진 배열을 적당히 크기별로 분리 후 분할하고 이것을 재귀적으로 반복한다.


 최악  평균 번의 비교를 수행한다.






















void quickSort(int data[], int l, int r) {
	int left = l;
	int right = r;
	int pivot = data[(l + r) / 2];
	
	while (left <= right) {
		while (data[left] < pivot) left++;
		while (data[right] > pivot) right--;
		if (left <= right) {
			
			int temp = data[left];
			data[left] = data[right];
			data[right] = temp;
			left++;
			right--;
		}
	}
	if (l < right) {
		quickSort(data, l, right);
	}
	if (r > left) {
		quickSort(data, left, r);
	}
}


BELATED ARTICLES

more