퀵 정렬 (Quick Sort)

1. 개요

• 분할 정복 전략을 사용하는 알고리즘이다.
• 주어진 배열에서 pivot을 설정하고 두 개의 부분 배열로 나눈다.
• pivot보다 작은 값은 pivot의 왼쪽 배열에, pivot보다 큰 값은 pivot의 오른쪽 배열에 둔다.
• 각 배열에 대해 재귀적으로 정렬을 수행한다.
• pivot 선택 방식에 따라 속도가 달라질 수 있다.

---

2. 특징

• 속도가 빠르다.
• 불안정 정렬이다.
• 시간복잡도: 평균 O(NLogN) / 최악 O(N^2)
• 배열이 이미 정렬되어 있는 경우(역순 포함), pivot이 가장 크거나 작은 값이 선택된다.
• 이 경우, 배열 분할이 불균형하게 발생하여 O(N^2)의 시간복잡도를 가진다.

---

3. 코드

import java.util.Arrays;

public class QuickSortTest {

	public static void main(String[] args) {
		int[] nums = { 3, 2, 7, 5, 11, 12, 1 };

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

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

	private static void quickSort(int[] arr, int left, int right) {
		if (left >= right) {
			return;
		}

		int pivot = partition(arr, left, right);

		quickSort(arr, left, pivot - 1);
		quickSort(arr, pivot + 1, right);
	}

	private static int partition(int[] arr, int left, int right) {
		int pivot = arr[left];
		int i = left;
		int j = right;

		while (i < j) {
			while (arr[j] > pivot && i < j) {
				j--;
			}
			while (arr[i] <= pivot && i < j) {
				i++;
			}
			swap(arr, i, j);
		}

		swap(arr, left, i);

		return i;
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}