[Sort]Quick Sort

- Unstable Sort

 

- 최악의 경우 O(N^2) // 평균적으로 O(nlogn)이지만 보장할 수 없다.

 

- 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

  --> 분할 정복 적용

 

1. 피봇을 보통 첫번째 원소로 잡고, Index가 1부터 n-1 을 탐색
2. 왼쪽에서 오른쪽으로(i=1 -> i++) 탐색하며 피봇보다 큰 값을 확인함과 동시에 오른쪽에서 왼쪽으로(j=n-1 -> j--) 탐색하며 피봇보다 작은 값을 확인한다.
3. i와 j 가 엇갈리지 않는다면 i와 j에 해당하는 값을 바꾼다.
4. 만약 엇갈린다면 지금 피봇값과 j 값을 바꾼다.
5. j 인덱스에 위치한 피봇값을 기준으로 왼쪽에는 피봇값보다 작은 요소들이, 오른쪽은 큰 요소들이 위치하게 된다.
6. 0~j-1 // j+1 ~ n-1 까지 재귀호출

void quick_sort(int arr[], int start, int end) {
	if (start >= end) return;


	int key = start;
	int i = start + 1;
	int j = end;

	int temp;
	
	while (i <= j) {
		// 엇갈릴때까지 반복
		while (arr[i] <= arr[key]) {
			i++;
		}
		while (arr[j] >= arr[key] && j > start) {
			j--;
		}
		if (i > j) {
			// key 값보다 작은걸 앞으로 빼내줘야 하니까 j 인덱스의 값을 앞으로
			temp = arr[j];
			arr[j] = arr[key];
			arr[key] = temp;
		}
		else {
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}

	}

	quick_sort(arr, start, j - 1);
	quick_sort(arr, j + 1, end);

}