⚡ 알고리즘 - 퀵정렬, 병합정렬, 힙정렬

🔹 퀵정렬(Quick Sort)

▫️ 개념

• 기준 원소(pivot)를 선택하여 배열을 두 부분으로 나누고, 왼쪽은 pivot 이하, 오른쪽은 큰 값이 되도록 분할한 뒤 재귀적으로 정렬하는 분할 정복 알고리즘

▫️ 시간 복잡도

• 평균: O(n log n)
• 최악: O(n²)
• 공간복잡도: O(log n)

🔹 특징

• 인-플레이스 정렬
• 불안정 정렬

🔹 예제 코드

public class QuickSort {
	public static void quickSort(int[] arr, int left, int right) {
		if (left >= right) return;
		
		int index = partition(arr, left, right);
		quickSort(arr, left, index - 1);
		quickSort(arr, index, right);
	}

	private static int partition(int[] arr, int left, int right) {
		int pivot = arr[(left + right) / 2];
		
		while (left <= right) {
			while (arr[left] < pivot) left++;
			while (arr[right] > pivot) right--;
			
			if (left <= right) {
				swap(arr, left, right);
				left++;
				right--;
			}
		}
		
		return left;
	}
	
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 8, 10, 1, 2, 1};
		quickSort(arr, 0, arr.length - 1);
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

🔹 병합정렬(Merge Sort)

▫️ 개념

• 배열을 반으로 나누어 각각 정렬 후 두 정렬된 배열을 병합하는 분할 정복 알고리즘

▫️ 시간 복잡도

• O(n log n)
• 공간복잡도: O(n)

▫️ 특징

• 안정 정렬
• 추가 메모리 사용

▫️ 예제 코드

public class MergeSort {
	public static void mergeSort(int[] arr, int left, int right) {
		if (left >= right) return;
		int mid = (left + right) / 2;
		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}

	private static void merge(int[] arr, int left, int mid, int right) {
		int[] temp = new int[right - left + 1];
		int i = left, j = mid + 1, k = 0;
		
		while (i <= mid && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		}
		while (i <= mid) temp[k++] = arr[i++];
		while (j <= right) temp[k++] = arr[j++];
		
		System.arraycopy(temp, 0, arr, left, temp.length);
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 8, 10, 1, 2, 1};
		mergeSort(arr, 0, arr.length - 1);
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

🔹 힙정렬(Heap Sort)

▫️ 개념

• 힙 자료구조를 이용해 최대값을 반복해서 제거하며 정렬하는 알고리즘

▫️ 시간 복잡도

• O(n log n)
• 공간복잡도: O(1)

▫️ 특징

• 불안정 정렬
• 일정한 성능 보장

▫️ 예제 코드

public class HeapSort {
	public static void heapify(int[] arr, int n, int i) {
		int largest = i;
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		
		if (left < n && arr[left] > arr[largest])
			largest = left;
		if (right < n && arr[right] > arr[largest])
			largest = right;
		if (largest != i) {
			int temp = arr[i];
			arr[i] = arr[largest];
			arr[largest] = temp;
			heapify(arr, n, largest);
		}
	}
	
	public static void heapSort(int[] arr) {
		int n = arr.length;
		for (int i = n / 2 - 1; i >= 0; i--)
			heapify(arr, n, i);
			
		for (int i = n - 1; i > 0; i--) {
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			heapify(arr, i, 0);
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 8, 10, 1, 2, 1};
		heapSort(arr);
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

🔹 비교

알고리즘	평균시간복잡도	최악시간복잡도	공간복잡도	안정성	특징
퀵정렬	O(n log n)	O(n²)	O(log n)	불안정	인-플레이스, 빠름
병합정렬	O(n log n)	O(n log n)	O(n)	안정	항상 일정 성능
힙정렬	O(n log n)	O(n log n)	O(1)	불안정	인-플레이스, 일정한 성능

🔹 참고

• 인-플레이스 정렬(In-place sorting)은 큰 메모리 공간 없이 주어진 배열 안에서 직접 데이터 위치를 바꿔서 정렬하는 방법을 의미한다.
• 불안정 정렬은 값이 같은 데이터의 순서가 바뀔 수 있음을 의미한다.