[ALGORITHM] QUICK SORT

---

이 버전에서는 TOC를 지원하지 않습니다. (ex. 모바일)

---

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} 순으로 나열된 배열이 있다고 가정한다면,

초기 배열

 

1차 탐색 좌측 & 우측

SWAP & 탐색 좌측 & 우측 #1

탐색 좌측 & 우측 #2

탐색 좌측 & 우측 #3

탐색 좌측 & 우측 #4 & 결과

---

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 + " =====================");
    }
    
}