[알고리즘] 퀵 정렬

[알고리즘] 퀵 정렬

2020. 5. 2. 23:12ㆍStudy/about Algorithm

정렬 알고리즘(Sorting Algorithm)이란, 대소 관계를 비교할 수 있는 항목에 따라 일정한 순서대로 순서가 있는 데이터의 원소들의 위치를 변경하는 작업입니다[1]. 이 중 퀵 정렬(Quick sort)에 대해 알아보도록 하겠습니다.

< 목 차 >

1. 알고리즘

2. 구현

3. 최적화

4. 시간 복잡도

* 특별한 언급이 없는 이상 오름차순 정렬을 기준으로 설명합니다 :)

* 본 글에서는 Python을 중심으로 설명합니다^[각주:1].

1. 알고리즘

퀵 정렬(Quick sort)은 토니 호어가 개발한 정렬 알고리즘으로, 분할 정복 알고리즘(Divide and conquer algorithm)의 대표적인 예입니다[1]. 여기서 분할 정복 알고리즘이란, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘을 일컫습니다[3]. 따라서 난수열에 대해 퀵 정렬을 실행하는 과정을 시각화한 [그림 1]을 보면, 오름차순으로 정렬하기 위해 계속해서 작은 단위로 나눠가며^[각주:2] 정렬이 진행됨을 확인할 수 있습니다.

이렇게 리스트를 작은 단위로 분할하기 위해서는 특정 기준이 있어야 할 것입니다. 퀵 정렬에서는 그 기준을 '피벗(Pivot)'이라 하며, 하나의 분할 과정을 '파티션(Partition)'이라 부릅니다.

다음과 같이 원소가 7개인 리스트를 가정해봅시다.

우선 이 중에서 하나의 원소를 고르고, 이를 피벗으로 설정합니다. 예시에서는 가장 첫 번재 원소를 골라 피벗으로 설정해보겠습니다.

피벗을 설정하게 되면 이제 비교 대상이 생긴 것과 마찬가지가 됩니다. 따라서 피벗 외의 모든 원소와 대소를 비교하여 피벗보다 작거나 같으면 피벗의 왼쪽에, 피벗보다 크면 오른쪽에 배치합니다. 이렇게 되면 피벗을 기준으로 리스트를 둘로 나눌 수 있게 됩니다([그림 2]^[각주:3] 참조).

분할을 마친 뒤 피벗은 고정되며(정렬 완료), 분할 된 리스트에 대해 계속해서 파티션을 적용해나가면 되는데 이때, 피벗의 왼편에 위치한 리스트를 먼저 계산합니다.

또 다시 왼편에 있는 리스트 먼저 파티션을 적용합니다.

이때, 세 번째 파티션의 경우에는 분할 된 리스트의 길이가 0 또는 1이 되었으므로 더 이상의 파티션을 진행하지 않습니다. 이렇게 왼편에 위치한 리스트에 대해 분할을 마무리 하였으니, 오른편에 위치한 리스트에 대해서도 똑같이 파티션을 진행해줍니다(본 과정은 위와 같으므로 생략하겠습니다). 따라서 파티션 과정을 한 번에 정리하여 표현하면 다음과 같습니다.

예제 1의 경우는 원소가 단 7개뿐이어서 간단하게 정렬을 완료할 수 있었습니다. 하지만 원소의 개수를 더 늘려 생각해보면 좀 더 복잡해집니다. 만약 다음과 같은 상황일 때, 세 번째 파티션을 마친 후 우리는 어떤 오른쪽 리스트를 선택하여 분할해야할까요? 두 번째 파티션에서 생성된 오른쪽 리스트로 가야할까요? 첫 번째 파티션에서 생성된 오른쪽 리스트로 가야할까요? 둘 다 '오른쪽 리스트'인 것은 분명합니다.

여기서 기억해야 할 것은 분할 정복 알고리즘은 '재귀적'이라는 것 입니다. 따라서 세 번째 파티션을 마무리하면 두 번째 파티션으로 올라가게 되고, 두 번째 파티션에서의 계산을 모두 마쳐야 첫 번째 파티션으로 접근 할 수 있는 구조인 것입니다. 즉, [그림 6]과 같은 경우에는 두 번째 파티션에서 생성된 오른쪽 리스트에 접근하여 또 다른 파티션을 진행하게 됩니다. 파티션 진행 순서를 총 정리하면 다음과 같습니다.

앞서 살펴보았던 예제들을 바탕으로 퀵 정렬 시 지켜야 할 규칙들을 정리해보면, 첫 번째로 무조건 왼편에 위치한 리스트 먼저 파티션을 진행하여야 하고, 두 번째로 더 이상 분할이 불가능 할 때 바로 윗 단계^[각주:4]의 오른편 리스트에 접근하여 분할해야 한다는 것 입니다. 이 두 가지만 확실히 기억해두시면 뒤에서 나올 재귀 함수의 작동 방식(계산 순서)를 이해하는데 도움이 됩니다 :)

다시 한 번 퀵 정렬 알고리즘에 대해 정리해보면 다음과 같습니다[2].

1. 리스트 가운데서 하나의 원소를 고르고, 이를 피벗으로 설정한다.

2. 피벗의 왼편에는 피벗보다 작거나 같은 원소들을 배치하고, 오른편에는 큰 원소를 배치하여 리스트를 둘로 분할한다. 이때, 분할을 마친 뒤에 피벗의 위치는 고정된다.

3. 분할된 두 개의 작은 리스트에 대해 리스트의 크기가 0이나 1이 될 때까지 재귀적으로 이 과정을 반복한다.

2. 구현

분할 된 리스트에 대해 분할이 가능하다면 계속해서 파티션을 적용하고, 그 길이가 0 또는 1이 되었을 때(분할이 더 이상 불가능 할 때) 바로 윗 단계로 접근하여 오른쪽 리스트에 대해 분할을 진행해주어야 합니다. 이런 경우에 쉽게 구현할 수 있는 방법은 무엇이 있을까요?

네. 바로 재귀 호출^[각주:5]을 이용하면 쉽게 구현할 수 있습니다. 먼저 수도 코드^[각주:6]를 통해 간단하게 구조를 살펴보겠습니다.

# pseudo code
procedure quickSort
    function quickSort(arr) :
        create a list named less
        create a list named greater
        
        if length(arr) <= 1 :
            return arr

        else :
            pivot = arr[0]

            for each x in arr[1:] do :
                if x <= pivot :
                    add x to less

                else :
                    add x to greater

                end if-else

            return concatenate(quickSort(less), [pivot], quickSort(greater))

            end for
        end if-else
    end function
end procedure

만약 함수에 들어온 리스트의 길이가 1보다 작다면 그 리스트를 반환하게 되며(정렬이 완료됨), 그렇지 않다면 파티션을 진행하게 됩니다. 이때, 본 코드에서는 피벗을 리스트의 첫 번째 원소로 지정하였으며, 이에 따라 for문의 조건 범위가 두 번째 원소^[각주:7]부터 시작하게 됩니다. for문에서는 피벗과 그 외의 원소들을 서로 비교하여 피벗보다 값이 작으면 'less'라고 선언된 리스트에, 값이 크면 'greater'라고 선언된 리스트에 저장하게 됩니다. 그 뒤 나눈 리스트를 재귀함수를 통해 다시 파티션 과정을 반복해주면서 정렬을 완료하는 구조입니다.

따라서 이를 Python을 통해 구현하면 다음과 같습니다.

"""
Quick sort, pivot position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def quickSort(arr) :
    n = len(arr)
    less = []
    greater = []
    
    if n <= 1 :
        return arr
    
    else :
        pivot = arr[0]
        
        for x in arr[1:] :
            if x <= pivot :
                less.append(x)
                
            else :
                greater.append(x)
                
        return quickSort(less) + [pivot] + quickSort(greater)

이때, 리스트 컴프리헨션(list comprehension)^[각주:8]을 이용하면 더 짧게 구현 가능합니다. 하지만, 리스트 컴프리헨션을 사용하는 경우에는 같은 arr 리스트에 대해 less와 greater에서 각각 조사를 진행하므로^[각주:9], 조금이나마 연산 과정을 줄이고 싶으신 분들에게는 위의 코드를 추천합니다.

"""
Quick sort, pivot position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def quickSort(arr) :
    n = len(arr)
    
    if n <= 1 :
        return arr
    
    else :
        pivot = arr[0]
        
        # Partition
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
                
        return quickSort(less) + [pivot] + quickSort(greater)

재귀함수가 어떻게 작동하는지 이해가 잘 안가신다면, 다음 영상과 같이 중간에 print문을 작성해서 파티션 과정을 하나하나 따라가보세요! 굳이 print문을 작성하지 않더라도 여기에서 각 step별로 리스트의 변화를 확인할 수 있습니다.

[영상 1] 예제 1, 정렬 과정 시각화 영상

3. 최적화

프로그램을 효율적으로 작성하기 위해서는 따져봐야 할 조건이 많습니다. 연산량이 많게되면 프로그램 실행 속도가 느려지므로 최소한의 연산을 할 수 있도록 작성하는 것이 좋고, 불필요한 변수를 많이 생성하게 되면 메모리 소모량이 크므로 꼭 필요한 변수만 선언하는 것이 좋습니다.

이를 바탕으로 앞서 우리가 구현한 퀵 정렬 소스코드를 살펴보면, 우리의 소스코드는 효율성이 그다지 좋지 않음을 파악할 수 있습니다. 우선, 재귀 호출시 less와 greater라는 리스트를 새로 생성하고, 마지막 return 시 리스트를 병합하는데 연산이 소요되기 때문입니다. 따라서 불필요한 작업을 최소한으로 줄여 효율적으로 프로그램을 작성해야 할 필요성이 있습니다.

그렇다면 less와 greater라는 리스트를 생성하지 않고 어떻게 구현할 수 있을까요? 그 아이디어는 다음과 같습니다.

앞서 구현한 소스코드에서 우리는 리스트의 첫 번째 원소를 피벗으로 설정하였지만, 피벗은 리스트 중 아무거나 정해도 되므로 가운데 원소를 피벗으로 선택해보겠습니다.

index 번호를 저장하는 변수를 2개를 선언하고, 양 끝에서 중앙쪽으로 한 칸씩 움직이며 피벗과의 대소 관계를 비교하는 검사를 하도록 설정합니다. 이때, 왼편에서부터 검사를 시작한 변수는 피벗보다 큰 원소를 찾고, 오른편에서부터 시작한 변수는 피벗보다 작은 원소를 찾습니다. 그 뒤 각각 큰 원소와 작은 원소를 찾게 되면 두 원소를 서로 교환합니다([그림 9]^[각주:10] 참조).

그 이유는, 알고리즘에 따르면 피벗의 왼편에는 피벗보다 작은 원소들만 위치해야하고 오른편에는 큰 원소들만 위치해야하기 때문에 "조건에 어긋난 원소들을 골라 서로 자리를 바꿔주겠다 "는 아이디어 입니다. 이 방식을 택하면 less와 greater라는 리스트를 굳이 생성하지 않아도 리스트를 분할 할 수 있게 됩니다.

이렇듯 계속해서 서로 알고리즘 조건에 어긋난 원소들을 골라 교환해줍니다(이때, 비교 대상에 피벗도 포함이 됩니다^[각주:11]). 그러다 left와 right변수가 엇갈리게 되면 교환을 멈추고 left를 새로운 분할 지점으로 설정하여 각각 새로운 파티션을 진행합니다([그림 10] 참조).

이 과정을 재귀 함수를 통해 반복해주면 정렬을 완료하게 됩니다. 먼저 수도 코드를 통해 간단하게 구조를 살펴보겠습니다.

# pseudo code
procedure quickSort
    function partition(arr, Index start position, Index end position) :
        pivot = middle element of array
        left = Index start position
        right = Index end position
        
        while left <= right :
            while arr[left] < pivot :
                left plus 1

            while arr[right] > pivot :
                right minus 1

            if left <= right :
                swap(arr[left], arr[right])
                left plus 1
                right minus 1
        end while
        
        return left
        
    end function

    function quickSort(arr, Index start position, Index end position) :
        left = Index start position
        right = Index end position
        
        if left >= right :
            return

        div = partition(arr, left, right)
        
        quickSort(arr, left, div-1)
        quickSort(arr, div, right)
        
    end function
end procedure

여기서, 최적화 전의 코드와는 다르게 quickSort 함수에 두 개의 매개변수(left, right)가 더 추가됨을 알 수 있습니다. 그 이유는, 최적화 된 코드에서는 새로운 리스트를 생성하지 않고 "본래의 리스트에서 자리바꿈을 통해 정렬 "해 나가기 때문에 검사해야 할 소분된 리스트의 인덱스 범위를 포함시킨 것입니다. 따라서 이를 통해 불필요한 리스트 생성과 더하기 연산을 제거할 수 있고, 이에 따라 소스 코드를 최적화 할 수 있습니다.

Python을 통해 구현해보면 다음과 같습니다.

"""
Quick sort Optimization, pivot position : arr[0], Ascending order

Created on Fri May 01 2020
    /*platform*/ Window 10
    /*python ver*/ 3.7

@author: Hannah_Noh
"""

def partition(arr, left, right) :
    pivot = arr[(left + right) // 2]
    
    while left <= right :
        # Finding indexes that do not meet algorithmic conditions.
        while arr[left] < pivot :
            left += 1
        while arr[right] > pivot :
            right -= 1
        
        if left <= right :
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1

    return left # Division criteria
        
def quickSort(arr, left, right) :
    if left >= right :
        return
    
    div = partition(arr, left, right)
    
    quickSort(arr, left, div-1)
    quickSort(arr, div, right)
    
    return arr

* main에서 quickSort 함수를 실행시킬 때는 전달인자를 다음과 같이 작성해주면 됩니다(첫 번째 파티션에서는 left가 첫 번째 원소, right가 마지막 원소이므로).

arr = [정렬하고자 하는 리스트]
result = quickSort(arr, 0, len(arr)-1)

4. 시간 복잡도

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킵니다[4]. 퀵 정렬 알고리즘은 여러 개의 파티션이 진행됨으로써 완료되는 정렬이기 때문에 최악/최선의 경우에 대한 설명을 하기에 앞서 하나의 파티션에서 발생하는 시간 복잡도에 대해 알아보겠습니다.

길이가 n인 리스트가 있다고 했을 때, 피벗을 기준으로 모든 원소에 대해 최소 한 번씩은 대소 비교를 진행해야 분할이 가능하므로 평균적으로 n번의 비교 및 자리 바꿈 연산이 이뤄집니다. 따라서 길이가 n인 리스트를 파티션 할 때 시간 복잡도는 O(n)이 됩니다.

파티션의 시간 복잡도가 이해되셨다면, 더 넓혀서 이제는 최악의 경우와 최선의 경우에 따른 퀵 정렬의 시간 복잡도를 알아보겠습니다.

1 ) 최악의 경우

최악의 경우는 피벗을 선택할 때 마다 한 쪽으로 치우쳐지는 경우입니다. 다음 [그림 11]을 살펴봅시다.

길이가 n인 리스트가 있다고 했을 때, 피벗을 선택할 때 마다 오른쪽으로 치우쳐진다고 가정하면 [그림 11]과 같이 n만큼 깊이들어가야 정렬을 완료할 수 있게 됩니다. 이때, 각 단계(층^[각주:12])에서의 연산 횟수를 따져 모두 더해보면 [그림 11] 우측 하단과 같은 결과를 얻게 됩니다(이때, c는 임의의 상수입니다^[각주:13]). 여기서 나머지 항은 무시되고 O(n²)인 이유는, 시간 복잡도는 n이 무한대로 갈 때를 가정하므로 n을 무시할 수 있을 만큼 n²이 가파르게 상승하여 시간 복잡도는 O(n²)이 됩니다.

이와 같은 경우의 예시로는 역순으로 정렬되어 있는 경우, 혹은 이미 정렬되어 있는 경우가 있습니다.

2 ) 최선의 경우

최선의 경우는 균등하게 분할되는 경우입니다. 다음 [그림 12]를 살펴봅시다.

길이가 n인 리스트가 있다고 했을 때, 깊어질수록 이전 단계의 리스트 길이를 1/2로 나누어 가지기 때문에 재귀 함수의 깊이는 다음과 같이 계산할 수 있습니다.

또한, 각 단계에서 연산 횟수를 각각 따져보면 cn이 됩니다(이때, c는 임의의 상수입니다). 따라서 cn번의 연산 횟수가 log n번의 층수만큼 반복되는 것 이므로 시간 복잡도는 O(n log n)이 됩니다.

3 ) 정리

따라서 퀵 정렬의 시간 복잡도를 정리해보면 다음과 같습니다.

최악	평균	최선
O(n²)	O(n log n)	O(n log n)

[ 참고 문헌 ]

[1] "정렬(1) -버블, 선택, 삽입, 퀵, 병합-" 강의자료, 이대원 교수님

[2] 퀵 정렬, 위키백과, <https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC>, (참고일 : 2020.05.02)

[3] 분할 정복 알고리즘, 위키백과, <https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98>, (참고일 : 2020.05.02)

[4] 시간 복잡도, 위키백과, <https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84>, (참고일 : 2020.05.02)

[5] Quicksort, CS 5 Fall 1996 Lectures, <https://www.cs.dartmouth.edu/~thc/cs5-F96/lec28.html>, (참고일 : 2020.05.02)

[ 각주 ]

(Python을 모르시는 분들을 위해) '리스트'라는 개념을 '배열'이라고 생각하시면 됩니다. 엄밀히 말하면 다른 의미이긴 하지만 :) [본문으로]
↔ 표시와 함께 표현된 회색 Box의 공간이 점점 작게 나눠지는 것을 확인하실 수 있습니다. [본문으로]
이때, 빨간색은 피벗을 의미합니다. [본문으로]
여기서 "단계"라는 표현이 적절치는 않습니다. 재귀 함수를 구조적으로 보았을 때 깊이 혹은 층수를 나타내기 위해 사용하였다는 것을 알려드립니다! [본문으로]
재귀 호출(Recursive call)이란, 함수가 자기 자신을 호출하는 것을 일컫습니다. [본문으로]
수도코드는 프로그램을 작성하기 전에 알고리즘의 모델을 대략적으로 모델링하는데 쓰이는 코드로, 특정 언어의 문법이 아닙니다 :) [본문으로]
index 번호로 하면 1번 [본문으로]
리스트 컴프리헨션은 리스트 안에 조건문, 반복문 등을 포함시켜 표현하는 방식입니다. 여러 줄의 코드를 한 줄로 줄일 수 있다는 강점이 있습니다. [본문으로]
위의 코드에서는 arr 리스트를 한 번씩만 훑게 되어있는데, 리스트 컴프리헨션을 사용하면 for문을 각각 써줘야 하므로 같은 리스트를 두 번 훑게 됩니다... [본문으로]
left는 왼편에서 피벗보다 큰 원소를 찾는 변수, right는 오른편에서 피벗보다 작은 원소를 찾는 변수를 의미합니다(여기서 left, right 변수는 바꿔야 할 원소의 인덱스 번호를 저장합니다). [본문으로]
그 이유를 묻는다면, 피벗은 "비교 대상"이 필요하기 때문에 설정한 것일 뿐, 그 자리가 고정된 것은 아니기 때문입니다. [본문으로]
[그림 11]에서 깊이(층수)를 의미한다. [본문으로]
각 파티션에서 n회 실행된다는 것은 평균적인 값 이므로 임의의 상수 c가 붙게 됩니다. [본문으로]

저작자표시

'Study > about Algorithm' 카테고리의 다른 글

[알고리즘] 버블 정렬 (0)	2020.05.02

[알고리즘] 버블 정렬 2020.05.02

냐쨩의 포트폴리오

냐쨩의 포트폴리오

태그

최근글

댓글

공지사항

아카이브

1. 알고리즘

2. 구현

3. 최적화

4. 시간 복잡도

1 ) 최악의 경우

2 ) 최선의 경우

3 ) 정리

[ 각주 ]

'Study > about Algorithm' 카테고리의 다른 글

관련글

티스토리툴바