개요

퀵 정렬이란 정렬 기법의 한 종류로서,
처음 배열에서 같은 요소들의 순서를 보장하지 않는
불안정 정렬 중 하나이다.

내가 구현한 방법은

• 맨 앞 값을 피봇(pivot)값으로 선택

• frontCursor을 피봇 바로 왼쪽값에서 시작해서
  피봇값보다 큰 값이 나올때까지 ++

• backCursor을 배열 맨뒤 값에서 시작해서
  피봇값보다 작은 값이 나올때까지 --

• 만약 위의 두과정이 끝났을 때, frontCursor값이
  backCursor값보다 같거나 커져서 엇갈리게 되면
  swap(arr[pivot], arr[backCursor]); 해준다.

  pivot값은 배열에서 정렬된값이므로
  quicksort(arr,arr+backCursor);
  quicksort(arr+backCursor+1,end);
  재귀함수를 호출한다.

• 엇갈리지 않았다면
  swap(arr[frontCursor], arr[backCursor]);
  한 후, frontCursor과 backCursor 엇갈릴 때까지
  반복한다.

시간복잡도는
pivot값을 제외한 그룹을 두 그룹으로 나눠서 비교하는 것을
(O(logN)) N번 반복하므로 총 O(NlogN)의 시간복잡도가 나온다.

최악의 시간복잡도는
정렬되어있는 배열에 대해 퀵 정렬을 수행할 때인데,
이때는 코드상으로 보면 두 그룹으로 나누질 못하고
매번 모든 요소를 비교해야하므로 O(n^2)의 시간복잡도가 나온다.

#include<iostream>

using namespace std;
int ex[6] = {3,8,7,0,1,6 };

void quicksort(int* arr,int* end) {		//시작 주소, 끝 다음 주소
	if (arr == end) return;				//arr+1했을때 end와 같다면 return
	int pivot = 0;						//pivot값 맨 처음값으로 둠
	int frontCursor = 1;				//pivot다음 커서
	int backCursor = (end - arr)-1;		//arr배열의 맨 마지막 요소 가리키는 커서

	while (frontCursor<=backCursor) {

		while (frontCursor<(end-arr)-1 && arr[frontCursor] < arr[pivot]) frontCursor++;		//pivot값보다 큰값나올때까지 frontcursor ++
		while (backCursor !=0 && arr[backCursor] >= arr[pivot]) backCursor--;				//pivot값보다 작은값나올때까지 backcursor--

		if (frontCursor >= backCursor) {													//만약 frontcursor와 backcursor 교차하거나 값이 같으면 
																							// ( 맨 처음값이 제일큰값이면 두 커서값이 같다 )

			swap(arr[pivot], arr[backCursor]);												// pivot값과 backcursor값 바꾸기
																							//재귀가 다끝나면 빠져나오기
		}
		else 
			swap(arr[frontCursor], arr[backCursor]);										//아니라면 frontcursor값과 backcursor값 변경해주기
	}
	quicksort(arr , arr+backCursor);														// 맨처음 pivot값은 제일 작은값으로 고정되었으므로 그다음 값부터 다시 반복
	quicksort(arr + backCursor+1, end);														// 맨처음 pivot값은 제일 작은값으로 고정되었으므로 그다음 값부터 다시 반복
}

int main() {
	quicksort(ex, ex + 6);
	for (int i = 0; i < 6; i++) {
		cout << ex[i] << " ";
	}
}