정렬 알고리즘(선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬)(Python - 파이썬)

---

선택 정렬(Selection Sort)

 컴퓨터가 데이터를 정렬 할 때를 생각해보면 데이터가 무작위로 여러개 있을 때, 이 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택하여 앞에서 두번째에 있는 데이터와 바꾸고... 이 과정을 반복하면 가장 원시적인 방법으로 매번 "가장 작은 것을 선택" 한다는 의미에서 선택정렬(Selection Sort)라고 한다.

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)) : # 리스트의 길이만큼 반복
    min_index = i # 가장 작은 원소의 인덱스(처음에는 i)
    for j in range(i+1, len(array)) : # i+1부터 끝까지 비교
        # 비교중인 인덱스(j)의 요솟값이 가장 작은 원소의 인덱스(min_index)의 요솟값
        # 보다 작을 경우 j와 min_index를 swap함(바꿔준다는 뜻)
        if array[min_index] > array[j] : 
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 위의 소스코드는 [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]를 요소로 가지는 리스트인 array를 선택 정렬을 이용하여 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]로 정렬하여 출력해주는 코드이다. 현재 인덱스(i)와 그 오른쪽 인덱스(j)부터 마지막 인덱스까지 계속하여 비교하며 현재 인덱스(i)보다 비교하는 인덱스(j)가 클 경우 둘의 위치를 바꿔주는 과정을 반복하여 정렬을 한다.

 선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 구현 방식에 따라서 약간의 오차는 있을 수도 있지만 위쪽의 예제 코드와 같은 경우에는 연산 횟수를 N + (N-1) + (N-2) + ... + 2로 볼 수 있다. 근사치로 N * (N+1) / 2 번의 연산을 수행한다고 가정하면 (N^2 + N) / 2 로 표현할 수 있다. 이는 빅오 표기법으로 간단히 O(N^2)라고 표현할 수 있다.

 따라서 선택 정렬의 시간 복잡도는 O(N^2)이다. 직관적으로 이해하자면 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이다. 시간 복잡도에 따라 정렬해야 할 데이터의 개수가 100배 늘어나면 이론적으로 수행 시간은 10000배로 늘어난다.

 그렇다면 이러한 시간 복잡도를 가진 선택 정렬이 얼마나 효율적인지 알아보자. 

 아래의 표는 파이썬 3.7의 선택 정렬 알고리즘과 이후에 다를 퀵 정렬 알고리즘 그리고 기본 정렬 라이브러리의 수행 시간을 비교한 표이다.

데이터의 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N = 100	0.0123초	0.00156초	0.00000753초
N = 1,000	0.354초	0.00343초	0.0000365초
N = 10,00	15.475초	0.0312초	0.000248초

 위의 표를 보면 선택 정렬을 이용하면 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격하게 느려지는 것을 확인할 수 있다. 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.

 선택 정렬은 기본 정렬 라이브러리를 포함하여 뒤에서 다룰 알고리즘과 비교하면 매우 비효율적이지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다. 그러므로 선택 정렬 소스코드를 자주 작성해보는 것이 좋다.

---

삽입 정렬(Insertion Sort)

 선택 정렬의 방식말고 다른 접근 방법에 대하여 생각을 해보자.

' 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?' 이러한 방식으로 정렬을 해 나가는 것을 삽입 정렬이라고 한다.

 삽입 정렬 또한 선택 정렬과 마찬가지로 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 삽입 정렬은 선택 정렬보다 구현 난이도는 높지만 실행 시간 측면에서는 더 효율적인 알고리즘이다. 

 특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬되어 있을 때' 굉장히 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸지만 삽입 정렬은 그렇지 않다. 

 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입' 한다는 의미에서 삽입 정렬(Insertion Sort0라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 후, 그 위치에 삽입된다는 점이 특징이다.

 삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두 번째 데이터부터 시작한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)) : # 삽입 정렬은 두 번째[1] 부터
    for j in range(i, 0, -1) : # 인덱스 i부터 1까지 감소하면서 비교
        # 왼쪽 값과 비교하여 더 작으면 한 칸씩 왼쪽으로 이동
        # 이 과정을 반복하면 가장 작은 값이 가장 왼쪽으로 이동
        if array[j] < array[j-1] :
            array[j], array[j-1] = array[j-1], array[j]
        else : # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                break
print(array)

 위의 소스코드는 삽입 정렬을 이용하여 정렬 후 출력해주는 코드이다. 삽입 정렬은 두번째 인덱스부터 비교하여 자신(j)과 비교할 값이자 왼쪽값(j-1)와 비교한 후 작으면 두 값을 바꾼 후 다시 왼쪽값과 비교를 하여 정렬을 해주는 방식이다. 반복이 진행될수록 가장 작은 값은 가장 왼쪽인덱스[0]으로 가며 두 번째로 작은 값은 가장 왼쪽에서 두 번째 인덱스[1]에 ...위치하게 된다.

 삽입 정렬의 시간 복잡도 또한 선택 정렬과 마찬가지로 O(N^2)이다. 반복문이 2번 중첩되어 사용되었기 때문이다. 실제로 수행 시간을 테스트해보면 선택 정렬과 흡사한 시간이 소요된다. 하지만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬된 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가지게 된다.

 다음에 배울 퀵 정렬 알고리즘과 비교해보면 보편적으로는 삽입 정렬이 비효율적이지만 정렬이 거의 되어 있는 상태에서는 퀵정렬 알고리즘보다 강력하게 동작한다.

---

퀵 정렬(Quick Sort)

 퀵 정렬은  위의 두 알고리즘보다는 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 '병합 정렬' 알고리즘이 있는데 이 '퀵 정렬' 알고리즘과 '병합 정렬' 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬 알고리즘! 어떠한 방식으로 동작하기 때문에 이름부터 "빠른 정렬" 알고리즘인지 알아보자.

' 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까? ' 퀵 정렬의 접근 방식이다.

 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이해하기까지 시간이 걸리겠지만 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다.

 퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 수와 작은 수를 교환할 때, 교환하기 위한 '기준'이 피벗이다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분 하는데, 여기서는 가장 대표적인 분할 방식인 호어 분할("Hoare Partition")방식을 기준으로 퀵 정렬을 설명한다. 호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다. 

 호어 분할 방식에서는 " 리스트에서 첫 번째 데이터를 피벗으로 정한다."

 이와 같이 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array) :
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1 :
        return array

    pivot = array[0] # 피벗(기준)은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    # 분할된 왼쪽 부분
    # 피벗보다 작거나 같으면 left_side로
    left_side = [x for x in tail if x <= pivot]
    # 분할된 오른쪽 부분
    # 피벗보다 크면 right_side로
    right_side = [x for x in tail if x > pivot]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 위의 코드는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드이다. 전통 퀵 정렬이 분할 방식과는 약간 다르다. 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이지만 더 직관적이고 기억하기 쉽다는 장점이 있다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end) :
    
    if start >= end : # 원소가 1개인 경우 종료
        return

    pivot = start # 피벗은 첫 번째 요소 / [0]
    left = start +1 # 피벗의 바로 오른쪽 요소 / [1] (인덱스를 나타냄)
    right = end # 마지막 요소 / [end] (인덱스를 나타냄)

    ''' 피벗을 뺀 상태 기준으로 left는 가장 좌측 인덱스[1]
        right는 가장 우측 인덱스[end] 
        left는 오른쪽으로 이동(+1), right는 왼쪽으로 이동하며(-1)
        array[left]의 값이 array[pivot]보다 큰 곳의 인덱스가 left
        array[right]의 값이 array[pivot]보다 작은 곳의 인덱스가 right
        이 상황에서 left가 right보다 크다면 엇갈렸다는(교차) 뜻 이므로 
        array[right]와 array[pivot]을 swap(교체)
        그렇지 않다면 array[left]와 array[right]를 swap(교체)
    '''
    while left <= right :

        # 피벗보다 큰 데이터를 찾을 때까지 반복(왼쪽 -> 오른쪽)
        while left <= end and array[left] <= array[pivot] :
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복(오른쪽 -> 왼쪽)
        while right > start and array[right] >= array[pivot] :
            right -= 1

        if left > right : # 엇갈렸다면(교차) 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)

quick_sort(array,0,len(array)-1)
print(array)

 위의 코드가 일반적으로 널리 쓰이는 직관적인 형태의 퀵 정렬 소스코드이다.

 앞서 본 선택 정렬과 삽입 정렬의 시간 복잡도는 O(N^2)였지만 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 선택 정렬과 삽입 정렬에 비해 매우 빠른 편이다.

 퀵 정렬에서 최선의 경우를 생각해보자. 피벗값의 위치가 변경되어 분할이 일어날 때마다 왼쪽 리스트와 오른쪽 리스트가 절반씩 분할된다면 어떨까? 데이터의 개수가 8개라고 가정하고 다음과 같이 정확히 절반씩 나눈다고 도식화를 해보면, 데이터 개수가 N(가로)이라면 높이는 약 logN이라고 판단할 수 있다.

 다시 말해 분할이 이루어지는 횟수가 기하급수적으로 감소하게 되는 것이다. 일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미하기 때문에 logN은 log2N을 의미하며 데이터 개수 N이 1,000일때 log2N은 10정도이다.

 데이터 개수가 많을수록 차이가 극명하게 드러난다. 다음 표를 보면 데이터의 개수가 많을수록 퀵 정렬은 앞서 다루었던 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작한다는 것을 추측할 수 있다.

아래의 표는 '평균 시간 복잡도'를 기준으로 각 정렬 알고리즘이 데이터의 개수에 따라 얼마나 많은 연산을 요구하는지를 보여주기 위하여 작성되었으며, 정확한 연산 횟수 비교는 아니다.

데이터의 개수(N)	N^2(선택 정렬, 삽입 정렬)	Nlog2N(퀵 정렬)
N = 1,000,000	≈ 1,000,000	≈ 10,000
N = 1,000,000	≈ 1,000,000,000,000	≈ 20,000,000

 다만, 퀵 정렬의 시간 복잡도에 대하여 한 가지 기억해둘 점이 있다. 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2)라는 것이다. 데이터가 무작위로 입력될 경우 퀵 정렬은 높은 확률로 빠르게 동작하지만 예시로 들었던 호어 분할 방식(리스트에서 첫 번째 데이터를 피벗으로 하는)을 사용하는 퀵 정렬 방식은 '이미 데이터가 정렬되어 있는 경우' 매우 느리게 동작한다.

 앞서 말한 삽입 정렬은 데이터가 정렬되어 있으면 빠르게 동작한다고 하였는데 그와 반대된다고 이해할 수 있다.

---

계수 정렬(Count Sort)

 계수 정렬(Count Sort) 알고리즘은 '특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘'이다.

 모든 데이터가 양의 정수인 상황을 가정해보자. 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행시간 O(N+K)를 보장한다. 계수 정렬은 이처럼 매우 빠르게 동작하면서 원리 또한 간단하다. 

 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용이 가능하다. 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우에는 계수 정렬을 사용하기가 어렵다.

 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용이  가능하다. 예를 들어 0 이상 100이하인 성적 데이터를 정렬할 때 계수 정렬이 효과적이다. 

 다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 계수 정렬은 사용할 수 없다.

 계수 정렬이 이런 특징을 가지는 이유는, 계수 정렬을 이용할 땐 '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'해야 하기 때문이다. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화 해야한다는 뜻이다. 여기서 1,000,000개가 아니라 1,000,001인 이유는 0 부터 1,000,000까지는 총 1,000,001개의 수가 존재하기 때문이다.

 계수 정렬은 앞에 설명했던 3가지 정렬 알고리즘(선택 정렬, 삽입 정렬, 퀵 정렬)처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)) :
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)) : # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]) :
        print(i, end = ' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
        # 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 출력

 위의 소스코드가 계수 정렬로 정렬하여 출력하는 코드이다. 

 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 

 앞서 언급했듯 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 해야하기 때문이다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 

 하지만 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들자면 데이터가 0과 999,999 단 2개만 존재한다. 이러한 경우에도 계수 정렬을 사용한다면 리스트의 크기가 100만개가 되도록 선언해주어야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 사용하기 적합하다.

---

나동빈 저자의 이것이 (취업을 위한) 코딩테스트다 with 파이썬 이라는 책으로 알고리즘을 공부하며 Chapter 06에 해당하는 정렬 알고리즘을 공부하면서 간략히 정리를 해보았습니다.