퀵 소트 Quick Sort

Intro::

퀵소트 정렬에 대해 알아보자.

정의

퀵소트(QuickSort)는 평균적인 상황에서 매우 빠른 실행 속도를 보이는 비교 기반 정렬 알고리즘입니다. 이 알고리즘은 '분할 정복' 전략을 사용하여 컬렉션(예: 배열)을 정렬합니다.

1. 분할(Divide): 배열에서 '피벗'이라는 하나의 요소를 선택합니다. 피벗을 기준으로 배열을 두 부분으로 나눕니다. 피벗보다 작은 모든 요소는 피벗의 왼쪽에, 피벗보다 큰 모든 요소는 피벗의 오른쪽에 오도록 합니다.

2. 정복(Conquer): 분할을 통해 생성된 두 부분 배열을 재귀적으로 정렬합니다.

3. 결합(Combine): 정렬된 부분 배열들을 결합하여 정렬된 전체 배열을 얻습니다. 퀵소트에서는 실제로 별도의 결합 단계가 필요 없습니다. 왜냐하면 배열이 제자리에서(in-place) 정렬되기 때문입니다.

시간복잡도

코드

package algorithm;

import java.util.*;

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

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

		while (i < j) {
			while (i <= high && arr[i] <= pivot) {
				i++;
			}
			while (j >= low && arr[j] > pivot) {
				j--;
			}
			if (i < j) swap(arr, i, j);
		}
		swap(arr, low, j);
		System.out.println(Arrays.toString(arr));
		System.out.println(low + " ~ " + high + ", i: " + i + ", j: " + j);
		return j;
	}

	public static void quickSort(int[] arr, int low, int high) {
		if (low < high) {
			int pivotIndex = partition(arr, low, high);
			quickSort(arr, low, pivotIndex - 1);
			quickSort(arr, pivotIndex + 1, high);
		}
	}

	public static void main(String[] args) {
		int[] arr = {6, 1, 4, 5, 3, 2};
		quickSort(arr, 0, arr.length - 1);
	}
}

References::