QuickSort에 대해서 알아봅시다~ Java Array, List 정렬 구현하기

정렬을 하는 알고리즘의 방식은 정말 많이 있습니다. 그리고 정렬만큼 복잡한 것도 없는 것 같습니다. 이제까지 사실 정렬이 나오면 그냥 sort 내장 함수를 적극적으로 활용하고, 그 원리에 대해서는 생각을 잘 하지 않았습니다. 그런데 결국 알아야 하긴 하니까.. 이해해야하긴 하니까.. 그리고 백준에서 정렬문제를 풀고 있어서 계속 정렬로 어떻게 하면 사람들을 괴롭힐지에 대한 문제만 나오니까.. 했지만 그래도 sort로 버티고 있었는데 결국 sort에 대해서 이해해야 하는 날이 오고 말았습니다.

 

1. 기본적인 sort 방법

가장 기본적인 sort의 방법은 Array의 모든 요소들을 비교해서 순서대로 정렬하는 방법입니다. 말 그대로 순차적으로 모든 요소를 하나하나 비교하게 되죠. 먼저 코드를 볼게요.

 

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 2, 3, 4};

        sortArray(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void sortArray(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

 

Array의 요소 갯 수만큼 반복문을 돌리고, 그리고 그 안에 또 다시 반복문을 넣는데 배열의 길이만큼에서 첫번째 반복문의 인덱스 값만큼 줄어들게 합니다. 그러면 위의 예제를 보면 총 21번의 반복을 하게 됩니다. 그리고, 이게 정렬을 시키는 방법은 첫번째 돌릴때 가장 큰 요소가 배열의 가장 오른쪽에 위치하게 되고, 그 다음 반복할 때 그 다음 큰 수가 차례대로 위치하게 되면서 정렬이 되는 방식입니다.

 

정렬은 되지만, 정말 많은 반복을 해야하죠. 작은 배열은 상관없지만 100개의 요소를 가진 배열이라고 한다면 총 5050번의 연산이 있어야 정렬이 됩니다. 그럼 조금 더 빠른 방법은 없을까요?

 

728x90

2. 퀵 정렬(Quick Sort)

자, 그럼 그 다음 알아볼 정렬은 퀵 정렬(Quick Sort)입니다. 재귀함수를 쓰는 방법입니다. 먼저 코드를 봅시다.

 

public class QuickSort {
    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;
    }
    
    static void quickSort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi-1);  
            quickSort(arr, pi+1, high); 
        }
    }

    public static void main(String args[]) {
        int arr[] = {10, 80, 30, 90, 40, 50, 70};
        int n = arr.length;
      
        quickSort(arr, 0, n-1);
      
        System.out.println("Sorted array: ");
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
}

 

먼저 partition이라는 함수와 quickSort라는 함수가 존재합니다. partition이라는 함수부터 살펴보도록 하겠습니다. patition 함수는 pivot이라는 변수와 i 변수를 갖게 되는데요. pivot은 호출할 때 넣은 매개변수의 배열의 가장 큰 index의 요소의 값을 대입합니다. 그리고 i 변수에는 low에 -1을 해서 넣습니다. 이 상황에서 반복문을 통해서 pivot의 수보다 작거나 같은 수를 찾고, 만약 찾으면 i에 1을 더하고, 작거나 같은 수를 배열의 i 번째 인덱스와 찾은 인덱스의 숫자를 교환합니다.

 

그리고 반복문이 끝나고 남은 i에 1을 더하고, 그 인데스의 숫자와 pivot의 기준이 된 배열의 인덱스의 숫자의 위치를 바꾸게 됩니다. 그럼 partition 함수가 실행되고 난 후에는 기준에 된 pivot의 좌측에는 pivot보다 작거나 같은 수가 위치하게 됩니다. 

 

그리고 quickSort함수에서 partition 함수를 호출하고, 반환받은 pi에 담긴 숫자를 통해서 quickSort함수를 low, pi-1, 그리고 pi+1, high를 매개변수로 집어넣으면서 재귀호출해서 나중에는 각각의 요소 하나만 갖는 배열로 쪼개지고 재귀호출이 멈추게 되면서 정렬이 됩니다.

 

참 어렵죠, 위의 예제를 실제로 계산하면 어떻게 되는지 한번 보도록 하겠습니다.

 

반응형

 

먼저, quickSort함수를 호출하면, partition(arr, 0, 6) 함수를 호출하게 됩니다. 그러면 pivot이 70, i는 -1이 됩니다.

 

그렇게 반복문을 통과하게 되면, 결과 배열은 {10, 30, 40, 50, 70, 80, 90}이 되고,  pi는 4가 담기게 됩니다. 그러면 quickSort(arr, 0, 3), quickSort(arr, 5, 6) 이렇게 다시 호출하게 됩니다. 그럼 처음에 피봇이 된 70을 기준으로 작은 수들의 배열, 큰 수들의 배열을 다시 quickSort 함수를 호출하게 됩니다.

 

그럼 첫번째 재귀호출을 보면 pivot은 50이 되고, pi에는 3이 담기게 되고, quickSort(arr, 0, 2), quickSort(arr, 4, 3) 이렇게 호출이 되는데 첫번째 재귀호출의 두번째 재귀호출은 high가 low보다 작으므로 종료, quickSort(arr, 0, 2)만 호출됩니다. 그렇게 계속, quickSort(arr, 0, 1), quickSort(arr, 0, 0)까지 호출되고, 종료되게 됩니다. 왜냐면 이미 정렬이 끝났기 때문입니다. 

 

두번째 재귀호출도 pivot은 90이 담기게 되고, pi는 6이 되면서 첫번째 재귀함수는 low와 pi - 1이 같아지면서 종료, 두번째 재귀함수도 pi+1이 high 보다 커지면서 종료되게 됩니다. 이렇게 결국에는 정렬이 됩니다.

 

상당히 복잡한 연산과정이지만, 한 번 전체적으로 어떻게 정렬이 되는지 공부해보니 조금은 알 것 같네요... 아는거 맞나?