[ALGORITHM] QUICK SORT
QUICK SORT 란
퀵 정렬(Quick Sort)은 가장 널리 사용되는 정렬 알고리즘 중 하나입니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방법을 사용하여 작동합니다. 퀵 정렬은 평균적으로 매우 빠른 실행 속도를 가지며, 대부분의 경우에 다른 정렬 알고리즘보다 효율적입니다.
퀵 정렬의 동작 방식은 다음과 같습니다:
배열에서 하나의 원소를 피벗(pivot)으로 선택합니다. 일반적으로 첫 번째 원소, 마지막 원소 또는 중간에 위치한 원소를 선택합니다.
피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 원소는 피벗의 왼쪽에, 큰 원소는 오른쪽에 위치하도록 배열을 재배치합니다.
분할된 두 개의 하위 배열에 대해 재귀적으로 위의 과정을 반복합니다. 각 하위 배열은 독립적으로 정렬됩니다.
재귀적인 호출이 완료되면 배열은 정렬이 완료됩니다.
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우(피벗이 항상 최솟값 또는 최댓값인 경우)에는 O(n^2)의 시간 복잡도를 가질 수도 있습니다. 하지만 퀵 정렬은 대부분의 실제 상황에서 매우 효율적으로 작동하며, 많은 정렬 알고리즘 중에서 가장 빠른 알고리즘 중 하나로 알려져 있습니다.
퀵 정렬은 다양한 프로그래밍 언어에서 구현될 수 있으며, 재귀적인 방식으로 구현하는 것이 일반적입니다. 이 알고리즘을 구현하려면 배열의 인덱스를 잘 조작하고 재귀 호출을 사용하여 분할과 정렬을 수행해야 합니다. 재귀 호출을 중단하는 조건은 하위 배열의 크기가 1 이하인 경우입니다.
퀵 정렬은 대용량의 데이터를 빠르게 정렬하는 데에 매우 유용하며, 많은 프로그래밍 문제에서 사용되는 정렬 알고리즘 중 하나입니다.
QUICK SORT 예시 설명
만약 아래와 같이 {3, 4, 1, 5, 7, 2, 6} 순으로 나열된 배열이 있다고 가정한다면,
QUICK SORT 소스
import java.util.Arrays;
import java.util.stream.Collectors;
public class QuickSort {
public static void main(String[] args){
// 대상 값 지정
int[] arr = {3, 4, 1, 5, 7, 2, 6};
// 퀵정렬 진행
quickSort(arr, 0, arr.length-1, 1);
// 결과 Array를 , 기준으로 Join하여 출력
String result = Arrays.stream(arr)
.mapToObj(String::valueOf)
.collect(Collectors.joining(", "));
System.out.print("퀵 정렬 결과 : " + result);
}
/**
* 퀵정렬
* @param arr 대상 배열
* @param minIdx 최소 값 위치
* @param maxIdx 최대 값 위치
* @param level 깊이 (표기를 위한 것일 뿐 필수는 아님)
*/
private static void quickSort(int[] arr, int minIdx, int maxIdx, int level){
System.out.println("===================== 퀵 정렬 시작 " + level + " =====================");
// 최소 값 위치가 최대 값 위치보다 크거나 같은 경우 더이상 탐색 하지 않음
if (minIdx >= maxIdx){
return;
}
System.out.println("입력 MIN " + minIdx + ", MAX " + maxIdx);
System.out.println("################### PIVOT 지정 ###################");
int pivotIdx = minIdx + (maxIdx - minIdx) / 2; // PIVOT 값 위치 산출
int pivotValue = arr[pivotIdx]; // PIVOT 값
System.out.println("PIVOT 위치 " + pivotIdx + ", 값 " + pivotValue);
// ################### 탐색 및 SWAP ###################
int leftIdx = minIdx; // 시작 left 위치 지정
int rightIdx = maxIdx; // 시작 right 위치 지정
// left 위치가 right과 같거나 커질 때까지 반복
while(leftIdx < rightIdx){
System.out.println("################### 왼쪽 탐색 ###################");
// left 값이 pivot값 보다 작은 경우 left 위치를 오른쪽으로 한 칸 이동
do {
int leftValue = arr[leftIdx];
System.out.println("LEFT 위치 " + leftIdx + ", 값 " + leftValue);
if(leftValue < pivotValue){
leftIdx++;
}else{
break;
}
} while(leftIdx < rightIdx);
System.out.println("################### 오른쪽 탐색 ###################");
// right값이 pivot값 보다 큰 경우 right 위치를 왼쪽으로 한 칸 이동
do {
int rightValue = arr[rightIdx];
System.out.println("RIGHT 위치 " + rightIdx + ", 값 " + rightValue);
if(rightValue > pivotValue){
rightIdx--;
}else{
break;
}
} while(leftIdx < rightIdx);
if(arr[leftIdx] > arr[rightIdx]){
System.out.println("################### SWAP ###################");
int temp = arr[leftIdx];
arr[leftIdx] = arr[rightIdx];
arr[rightIdx] = temp;
// 현재 값이 Pivot값이 아닌 경우 한칸 이동
if(arr[leftIdx] != pivotValue) leftIdx++;
if(arr[rightIdx] != pivotValue) rightIdx--;
}
}
// 끝이 시작보다 큰 경우 배열 좌측 정렬
if(leftIdx > minIdx){
System.out.println("################### 좌측 분할 정렬 ###################");
quickSort(arr, minIdx, leftIdx, level + 1);
}
// 시작이 끝보다 작은 경우 배열 우측 정렬
if(leftIdx + 1 < maxIdx){
System.out.println("################### 우측 분할 정렬 ###################");
quickSort(arr, leftIdx + 1, maxIdx, level + 1);
}
System.out.println("===================== 퀵 정렬 종료 " + level + " =====================");
}
}