퀵정렬

퀵정렬

• 주어진 배열을 두 개로 분할하고, 각각을 정렬한다.
• 불안정 정렬
• 시간 복잡도 O(nlogn), 최악의 경우 (n2)

병합 정렬과 다른 점

• 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기준 아이템 (pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.
• 각 부분 정렬이 끝난 후, 병합정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않는다.

동작과정

1. 정렬한 배열 입력받기
2. 임의의 한점을 pivot으로 선정 (Partition 방법)
   - pivot보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동
3. 정렬할 범위가 0이나 1이 될 때까지 분할 정복

* Partition 방법에 따라 Hoare-partition 알고리즘, Lomuto-partition 알고리즘 두 가지 종류가 있다.

Hoare-partition 알고리즘

• pivot은 가장 왼쪽 값으로 선정 (왼쪽, 오른쪽, 중간값 상관없음)
• L: pivot 보다 작거나 같으면 증가, pivot 보다 큰값을 만날 때까지 이동
• R: pivot 보다 크면 감소, pivot 보다 작거나 같은 값을 만날 때까지 이동

---

import java.util.Arrays;

public class QuickSort_Hoare {
	public static void main(String[] args) {
		int[] arr = { 77, 32, 37, 17, 22, 8, 13, 42, 26 };

		quickSort(arr, 0, arr.length - 1);

		System.out.println(Arrays.toString(arr));
	}

	// Quick Sort
	public static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int pivot = partition(arr, left, right);
			quickSort(arr, left, pivot - 1);
			quickSort(arr, pivot + 1, right);
		}
	}

	// Hoare-partition
	public static int partition(int[] arr, int left, int right) {
		// 가장 왼쪽 값을 pivot으로 설정
        int pivot = arr[left];

		// 시작구간은 pivot 한 칸 옆부터 끝까지
		int L = left + 1, R = right; 
		int tmp;
		
		// 교차가 되는 순간 멈추기
		while (L <= R) {
			// L : pivot 보다 큰값을 만날 때까지 이동
			// 앞에 조건을 빼면 안되는 이유는? ({33,99,99};
			while(L<=R && arr[L] <= pivot) L++;
			// R : pivot 보다 작거나 같은 값을 만날 때까지 이동
			while(arr[R] > pivot) R--;
			
			// L과 R의 값 서로 바꾸기
            // L과 R이 아직 교차되지 않았다면
			if(L<R) {
				tmp = arr[L];
				arr[L] = arr[R];
				arr[R] = tmp;
			}
		}
        
        // L과 R이 교차가 일어나서 끝났을 때
		// pivot이 가리키는 값과 R이 가리키는 값을 바꾸어 pivot의 위치를 결정
        // *pivot의 위치를 가장 왼쪽의 값으로 설정했기 때문에 R이 가리키는 값과 교환
		tmp = arr[left];
		arr[left] = arr[R];
		arr[R] = tmp;
		
        // 💡 R을 리턴하는 이유
		return R;
	}
}

---

💡 R을 리턴하는 이유
 L과 R이 교차가 되었다는 것은 그 지점이 경계라는 의미. 
 따라서 (가장 왼쪽 값을 pivot으로 설정했기 때문에) arr[R]과 pivot을 바꾸고,
 다음 pivot(정렬 기준)을 리턴