퀵 정렬(Quick Sort)

퀵 정렬의 개념

퀵 정렬은 다음과 같은 원리로 동작합니다.

1. 기준점 선택: 배열에서 기준점(pivot)을 선택합니다. 이 기준점을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할됩니다.
2. 분할: 배열을 기준점을 중심으로 두 그룹으로 분할합니다. 왼쪽 그룹은 기준점보다 작은 값들로, 오른쪽 그룹은 기준점보다 큰 값들로 구성됩니다.
3. 정복: 분할된 그룹을 재귀적으로 퀵 정렬을 적용합니다. 각 그룹에서도 기준점을 선택하고 분할, 정복을 반복합니다.
4. 결합: 정렬된 그룹을 결합하여 정렬된 배열을 얻습니다.

자바로 퀵 정렬 구현하기

자바를 사용하여 퀵 정렬을 구현해보겠습니다. 아래는 퀵 정렬을 자바 코드로 구현한 예시입니다.

public class QuickSort {

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

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        
        System.out.println("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

코드 해설

• quickSort 메소드는 배열과 배열의 시작 인덱스(low)와 끝 인덱스(high)를 입력으로 받아 퀵 정렬을 수행합니다.
• partition 메소드는 배열을 기준점을 중심으로 두 그룹으로 분할하고, 기준점의 새 위치를 반환합니다.
• main 메소드에서는 퀵 정렬을 호출하고, 정렬된 배열을 출력합니다.

실행 결과

위의 코드를 실행하면, 주어진 배열이 퀵 정렬을 통해 정렬되고, 정렬된 배열이 출력됩니다.

 

정렬된 배열:
5 6 11 12 13

 

 

퀵 정렬 알고리즘의 개념과 자바로의 구현에 대해 자세히 살펴보았습니다. 퀵 정렬은 대용량 데이터를 빠르게 정렬하는 데 효과적인

알고리즘으로, 정렬 알고리즘 중에서도 빠른 속도로 작동합니다.