[정렬 알고리즘] 퀵 정렬(Quick Sort): 개념과 자바 예제 코드

🐥 퀵 정렬이란?

퀵 정렬은 "빨리 정렬하기 위해 만들어진 방법"이에요. 🎯 이름처럼 빠르고 효율적인 알고리즘 중 하나랍니다!
어떻게 동작하는지 피자 조각을 나누는 방법으로 비유해서 쉽게 설명해볼게요. 🍕

---

🧐 퀵 정렬의 핵심 아이디어

1. 피벗(Pivot)을 정하기
   • 피벗은 기준점이에요. 🍀 (예: 피자 한 조각을 "기준"으로 선택해본다고 가정)
2. 작은 조각과 큰 조각으로 나누기
   • 피벗보다 작은 값을 왼쪽, 큰 값을 오른쪽으로 나눠요.
   • 나누기 작업을 계속 반복하면 정렬이 끝나요! ✨
3. 재귀적으로 반복
   • 작은 조각, 큰 조각에 대해 다시 피벗을 정하고 나누는 걸 반복합니다.
   • 최종적으로 모든 조각이 제자리를 찾아요.

---

🛠 어려운 용어를 쉽게 이해하기

• 재귀(Recursion):
  큰 문제를 작은 문제로 나누어 반복적으로 해결하는 방법.
  (예: 큰 피자를 계속 반으로 자르다 보면 한 입 크기가 되듯이!)
• 피벗(Pivot):
  정렬의 기준이 되는 값. "이걸 중심으로 나눌게요!"라는 기준점이에요. 🧸

---

🖥️ 코드로 이해하기

1. Java

// 🐣 퀵 정렬 예제
public class QuickSortExample {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) { // 🍀 배열의 크기가 1보다 클 때만 진행
            int pi = partition(arr, low, high); // 🧩 피벗을 기준으로 나누기
            quickSort(arr, low, pi - 1);  // 피벗 왼쪽 정렬
            quickSort(arr, pi + 1, high); // 피벗 오른쪽 정렬
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 🎯 마지막 요소를 피벗으로 선택
        int i = low - 1; // 작은 값을 넣을 위치 초기화

        for (int j = low; j < high; j++) { // 배열을 순회하며
            if (arr[j] < pivot) { // 🍕 피벗보다 작으면
                i++;
                int temp = arr[i];
                arr[i] = arr[j]; // 자리 바꾸기
                arr[j] = temp;
            }
        }

        // 🍕 피벗을 올바른 위치로 이동
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // 피벗 위치 반환
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5}; // 예제 배열
        quickSort(arr, 0, arr.length - 1); // 정렬 시작
        for (int num : arr) {
            System.out.print(num + " "); // 🐥 결과 출력
        }
    }
    // 입력 배열: {10, 7, 8, 9, 1, 5}
    // 출력:
    1 5 7 8 9 10
}

---

2. Python

# 🐥 퀵 정렬 예제
def quick_sort(arr):
    if len(arr) <= 1:  # 🍀 리스트 크기가 1 이하일 경우 이미 정렬됨
        return arr
    pivot = arr[len(arr) // 2]  # 🎯 중간 값을 피벗으로 선택
    left = [x for x in arr if x < pivot]  # 🍕 피벗보다 작은 값들
    middle = [x for x in arr if x == pivot]  # 🍀 피벗과 같은 값들
    right = [x for x in arr if x > pivot]  # 🍕 피벗보다 큰 값들

    # 🎡 왼쪽, 중간, 오른쪽을 합쳐 정렬된 리스트 반환
    return quick_sort(left) + middle + quick_sort(right)

# 예제 배열
arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr))  # 🐥 정렬된 결과 출력
# 입력 배열: [10, 7, 8, 9, 1, 5]
# 출력:
[1, 5, 7, 8, 9, 10]

---

💡 한눈에 정리 (퀵 정렬의 특징)

• 시간 복잡도:
  • 평균: O(n log n)
  • 최악: O(n²) (피벗을 항상 잘못 선택할 경우)
• 장점: 빠르고 효율적, 추가 메모리가 거의 필요 없음!
• 단점: 피벗을 잘못 선택하면 비효율적. 😥

---

🐾 마무리

퀵 정렬은 마치 요리할 때 재료를 종류별로 분류한 뒤, 다시 정리해서 접시에 예쁘게 담는 것과 비슷해요. 🍳
어려워 보일 수도 있지만, 직접 코드를 실행하면서 이해하면 "생각보다 간단하네!" 하고 느낄 거예요! 😊

 

2024.12.14 - [자료구조 및 알고리즘] - [쉬운설명] 병합 정렬 (Merge Sort) : 예시 코드

[쉬운설명] 병합 정렬 (Merge Sort) : 예시 코드

2024.12.14 - [자료구조 및 알고리즘] - [쉬운설명] 삽입 정렬(INSERT SORT) : 예시 코드

[쉬운설명] 삽입 정렬(INSERT SORT) : 예시 코드