1. 퀵 정렬이란?

퀵 정렬은 분할 정복(Divide and Conquer)방식의 대표적인 정렬 알고리즘으로, 기준 값(피벗)을 중심으로 작은 값과 큰 값을 나누어 정렬하는 방식입니다.
평균 시간 복잡도가 O(nlogn)으로 빠르며 메모리 사용이 적습니다. 최악의 경우에 O(n^2)가 될 수 있습니다.

2. 퀵 정렬 동작 원리

• 피벗 : 배열의 임의의 요소를 피벗으로 설정하고, 피벗을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치합니다.
• 재귀적 분할 : 피벗을 기준으로 배열이 두 부분으로 나뉜 후 각 부분 배열을 재귀적으로 정렬합니다.

3. 퀵 정렬 예제 코드(Java)

import java.util.Arrays;


public class QuickSort {

    // 퀵 정렬 메서드 : 배열과 왼쪽/오른쪽 인덱스를 받아 재귀적으로 정렬 수행
    public static void quickSort(int[] arr, int left, int right) {
        // 배열을 계속 나누기 위해 왼쪽 인덱스가 오른쪽보다 작은 경우에만 실행
        if (left < right) {
            // partition 메서드를 호출하여 피벗을 기준으로 배열을 분할하고
            // 피벗의 위치 인덱스를 반환받음
            int pivotIndex = partition(arr, left, right);

            // 왼쪽 부분 배열을 재귀적으로 정렬
            quickSort(arr, left, pivotIndex - 1);
            // 오른쪽 부분 배열을 재귀적으로 정렬
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    // 분할 메서드 : 배열을 피벗을 기준으로 두 부분으로 나누는 역할
    private static int partition(int[] arr, int left, int right) {
        // 피벗을 배열의 마지막 요소로 설정
        int pivot = arr[right];
        // i는 피벗보다 작은 요소가 모일 마지막 위치 인덱스
        int i = left - 1;

        // 왼쪽부터 오른쪽 끝 바로 전까지 탐색
        for (int j = left; j < right; j++) {
            // 현재 요소가 피벗보다 작으면
            if(arr[j] < pivot) {
                // 작은 값을 찾았으므로 i 증가 후 i와 j 위치의 요소를 교환
                i++;
                swap(arr, i, j);
            }
        }
        // 피벗을 올바른 위치에 놓기 위해 i+1 위치의 요소와 교환
        swap(arr, i+1, right);
        // 최종적으로 피벗의 위치 인덱스를 반환;
        return i+1;
    }

    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 = {9, 4, 7, 6, 3, 1, 5};
        System.out.println("원본 배열 : "+ Arrays.toString(arr));

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

        System.out.println("정렬한 배열 : "+ Arrays.toString(arr));
    }
}

4. 코드 실행 과정 설명

초기 호출
quickSort(arr, 0, arr.length - 1)을 호출하여 left = 0, right = 6으로 퀵 정렬을 시작합니다.

첫 번째 partition(arr, left, right) 호출

• 배열 : {9, 4, 7, 6, 3, 1, 5}
• left = 0, right = 6
• 피벗: arr[6] = 5
• 초기 인덱스: i = left-1 -> i = -1

1. j = 0에서 arr[0] = 9는 5보다 크므로, i는 그대로이고 교환이 일어나지 않음.
2. j = 1에서 arr[1] = 4는 5보다 작으므로 i를 0으로 증가시키고 swap(arr, 0, 1)을 호출하여 9와 4를 교환합니다.
   • 배열 상태: {4, 9, 7, 6, 3, 1, 5}
3. j = 4에서 arr[4] = 3은 5보다 작으므로 i를 1로 증가시키고 swap(arr, 1, 4)를 호출하여 9와 3을 교환합니다.
   • 배열 상태: {4, 3, 7, 6, 9, 1, 5}
4. 모든 비교 후, swap(arr, 3, 6)으로 피벗 5의 위치를 이동시켜 배열은 {4, 3, 1, 5, 9, 7, 6}가 됩니다.
   이후 단계 반복
   이제 배열이 두 부분으로 나뉘었으므로 각각에 대해 quickSort를 재귀적으로 호출하여 반복 정렬합니다. 각 부분 배열에 대해서도 partition을 통해 피벗을 선택하고 정렬을 반복합니다.