알고리즘] 퀵 정렬(Quick Sort)

void quickSort(int* data, int start, int end) {
	if (start >= end) return;

	int pivot = start;
	int left = start + 1, right = end, temp;

	while (left <= right) { //만약 left>right로 엇갈린다면 끝내게
		while (left <= end && data[left] <= data[pivot]) { left++; }
		while (right > start && data[right] >= data[pivot]) { right--; }
		if (left > right) { //꼬였을 경우(큰 값 인덱스>작은 값 인덱스) 작은값과 key값을 swap한다
			//right와 pivot이 바뀐 이유는 pivot이 배열의 맨 앞 인덱스라는 가정 하에서 
			//right는 작은 값, left는 큰 값을 나타낸다. 
            //pivot, right,left순이라고 할때 pivot과 left를 swap하면
			//left의 큰 값이 배열의 맨 앞으로 가므로 right와 pivot을 swap해야 한다.
			temp = data[right];
			data[right] = data[pivot];
			data[pivot] = temp;
		}
		else { //꼬이지 않았을 경우 큰값과 작은값을 swap한다 
        	//>> 작은값은 왼쪽으로, 큰값은 오른쪽으로
			temp = data[left];
			data[left] = data[right];
			data[right] = temp;
		}
	}

	quickSort(data, start, right - 1);
	quickSort(data, right + 1, end);
}

int main() {
	int N;
	scanf("%d", &N);
	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	quickSort(arr, 0, N - 1);
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
	delete[] arr;
}

최선, 평균 O(nlogn)

최악 O(n^2) : 이미 정렬돼서 계속 한쪽으로 치우친 배열로 조합될 경우

---

▼참고

5. 퀵 정렬(Quick Sort)