정렬알고리즘 2탄. Quick Sort (퀵 정렬)

Zn's Log·2023년 7월 3일

정렬 정렬알고리즘 퀵소트

정렬 알고리즘

목록 보기

1/1

들어가며

오늘 이야기해볼 정렬은 정말 중요한, 정렬에 대해 배웠다면 누구든지 들어본 적 있지만, 어떻게 되는지는 잘 모르는 그 정렬. 퀵소트이다.

초급자부터, 직접 코드를 짜보는 것까지 순서대로 알아보자!

퀵소트에 대해

퀵 소트는 분할 정복 알고리즘 을 기반으로 정렬되는 방식이다. 분할하고, 분할한 요소들을 정복해가면서 정렬을 진행한다. 이따 진행방식을 살펴보고 나면 좀 더 쉽게 이해될 것이다.
퀵정렬의 시간 복잡도는 최악의 경우 O(N^2), 평균 O(NlogN) 이다. (비슷하게 분할정복을 사용하는 병합정렬과 비교하자면, 일반적으로 퀵정렬이 빠르다)
정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지않으므로 제자리 정렬 이다.
데이터를 비교하면서 정렬을 진행하기 때문에 비교 정렬 이다.
하나의 피벗을 두고 두개의 부분 리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정 정렬 이다.
자바의 Arrays.sort() 함수는 퀵소트를 기반으로 한다.
( java의 경우 듀얼 피봇 퀵소트 사용)

초급자 버전 ( 원리 이해하기 )

간단하게 설명하자면 퀵소트에서 제일 중요한 건 Pivot(피봇) 이다.
퀵소트는 이 피봇을 중심으로 정렬을 진행한다.

피봇을 중심으로 모든 값을 검사하면서 작은건 피봇 왼쪽에, 큰건 피봇 오른쪽에 배치한다.
이로써 피봇의 위치를 확정하고 피봇 왼쪽 배열에서 새로운 피봇 하나, 피봇 오른쪽 배열에서 새로운 피봇하나를 골라 다시 진행한다
이렇게 계속 분할해서 진행하며, 배열을 쪼갤 수 없을 때까지 진행하면 정렬 완성.

중급자 버전 ( 실제로 어떤 식으로 진행되는지 알아보기 )

피봇 선정에 대하여

퀵정렬의 시간복잡도는 최악의 경우 O(N^2), 평균 O(NlogN)이다.
이 때 시간복잡도를 결정짓는 큰 요소는 바로 피벗값을 어떻게 선정하느냐이다.
만약 이미 정렬된 배열에서 처음값을 피벗으로 삼게된다면
(n-1)n으로 O(n^2)이 된다.

피봇 선정은 앞서 말했듯이 첫번째 값이나 마지막 값을 피벗으로 선정할수도 있고
첫번째 값, 가운데 값, 마지막 값 중에 중간값을 피벗으로 선정하는 방법(Median of Three)
랜덤 값을 피벗으로 선정하는 방법 등이 있다.

이 중 Median of Three 방법을 쓰는게 비교적 효과적이라고 한다.

실제 진행 방향 살펴 보기

고급 ( 직접 코드 작성해보기 )

import java.util.Arrays;

public class Sort_Algorithm {
    static int[] arr = {5,7,9,0,3,1,6,2,4,8,11};
    public static void main(String[] args) {
        arr = new int[] {5,7,9,0,3,1,6,2,4,8,11};

        System.out.println("Original Arr: "+Arrays.toString(arr));
        QuickSort(arr,0,arr.length-1);
        System.out.println("Sort Arr: "+Arrays.toString(arr));
        System.out.println();
    }
    public static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    private static void QuickSort(int[] arr, int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        System.out.print("pivot : " +arr[lo]);
        int pivot = partition(arr, lo, hi);
        System.out.println(" arr : "+Arrays.toString(arr));

        QuickSort(arr, lo, pivot - 1);
        QuickSort(arr, pivot + 1, hi);
    }

    private static int partition(int[] arr, int left, int right) {

        int lo = left+1;
        int hi = right;
        int pivot = left; // 부분리스트의 왼쪽을 피벗으로 설정

        // lo가 hi보다 작거나 같을 때 까지만 반복한다.
        while(lo <= hi) {
            while(arr[lo] <= arr[pivot] && lo <= hi) {
                lo++;
            }
            while(arr[hi] > arr[pivot] && lo <= hi) {
                hi--;
            }
            if(lo>hi){
                swap(arr,pivot, hi);
            }else{
                swap(arr, lo, hi);
            }
        }
        return hi;
    }
}

이렇게 작성을 해서 프로그램을 돌리면

잘 보면 피봇을 기준으로 왼쪽에 작은, 오른쪽에 큰 요소들이 잘 배치되는 것을 볼 수 있다.

마치며

다양한 정렬 알고리즘 중 꽤 효율적이며 실제로도 자바의 Arrays.sort() 알고리즘에 사용될정도로 중요한 퀵소트에 대해 공부해보는 시간을 가졌다. 정렬을 하다가도 자꾸 까먹게 되는데 이렇게 정리하면서 어떤식으로 진행하는지 꼼꼼히 살펴보고 실제로 코드 작성도 해보는 시간을 가지니 좋았다. 다음에는 TimSort 알고리즘에 대해서도 공부해보고 싶다.

Reference

Zn's Log

정렬알고리즘 2탄. Quick Sort (퀵 정렬)