퀵 정렬( QuickSort )

 퀵 정렬

1. 퀵 정렬이란? 

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

- 자료 출처 : 위키 백과

퀵 정렬의 정의 만큼은 위키 백과의 자료를 보고 이해하는 것이 좋다고 생각합니다.

하지만 저 같은 경우에는 아래의 위키 백과의 Java 퀵 정렬 소스는 직관적이지 않다고 생각했습니다.

public void quickSort(int[] arr, int left, int right) {
    int i, j, pivot, tmp;

    if (left < right) {
        i = left;
        j = right;
        pivot = arr[left];
        //분할 과정
        while (i < j) {
            while (arr[j] > pivot) j--;
            // 이 부분에서 arr[j-1]에 접근해서 익셉션 발생가능함
            while (i < j && arr[i] <= pivot) i++;

            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        arr[left] = arr[i];
        arr[i] = pivot;
        //정렬 과정
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

그래서 퀵 정렬을 이해하고 최대한 직관적으로 소스 코드를 작성해보았습니다.

QuickSort class 안에 main 함수입니다.

메인 함수에서는 정렬하게 될 배열, 그리고 퀵 정렬 기능을 하게될 quickSort 메소드가 있습니다.

마지막으로 for문을 통해서 결과를 출력하고 있습니다.

public class QuickSort {
    public static void main(String[] args) {

        int[] arr = {66, 10, 1, 34, 5, -10};
        

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

        for (int k = 0; k <= arr.length - 1; k++) {
            System.out.print("" + arr[k] + " ");
        }
    }

아래 partition은 말 그대로 퀵 정렬에서 피봇 좌측에는 피봇보다 작은 원소들을, 우측에는 피봇보다 큰 원소들을 배치하기 위해 필요한 메소드입니다.

피봇은 좌측 끝, 우측 끝, 중앙 모두로 설정하는 것이 가능합니다. ( 저는 중앙값으로 하는 것이 가장 이해하기가 쉬웠습니다, )

피봇 좌측에서는 피봇보다 큰아이템을 찾고, 피봇 우측에서는 피봇보다 작은 원소를 찾으면 while문을 벗어나고 tmp를 사용하여 둘의 위치를 바꿉니다.

만약 left, right가 교차하게 된다면 right를 반환합니다. 여기서 right나 left를 반환해도 상관없습니다.

 (제가 해본 결과 상관없었지만 혹시 예외 상황이 있다면 말씀해주시면 감사하겠습니다.)

public static int partition(int[] arr, int left, int right) {
        int pivot = arr[(left + right) / 2];  
//pivot은 중위법( 좌측 끝, 우측 끝, 중앙 모두 가능 )
//        int pivot = arr[left];
//        int pivot = arr[right];
        int tmp;

        while (left < right) {
            while (left < right && arr[left] < pivot) left++;
            while (left < right && arr[right] > pivot) right--;

            if (left < right) {
                tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        
          return right;  
//        return left;
    }

qucikSort 메소드입니다. main 메소드에서 quickSort를 실행시키게 되면 partition 메소드를 통해 리턴 받은 값을 pivotNewIndex 값으로 설정합니다.

pivotNewIndex는 새로운 피봇을 의미하고,

quickSort 메소드를 실행하며 피봇의 우측과 좌측 원소들을 정렬합니다.

public static void quickSort(int[] arr, int left, int right){

        if(left<right){
            int pivotNewIndex = partition(arr,left,right);

            quickSort(arr,left,pivotNewIndex-1);
            quickSort(arr,pivotNewIndex+1,right);
        }
    }
}

혹시나 잘못된 부분이나, 궁금하신 점에 대한 댓글은 언제든 환영입니다 !

읽어주셔서 감사합니다.