[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter6(1). 정렬

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

프로그램에서 데이터를 가공할 때 대부분 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬을 공부하면 '알고리즘의 효율성'도 쉽게 이해할 수 있다.

 

 면접에서도 단골 문제로 출제되니 꼭 기억해두자.

데이터를 보고 우리의 뇌는 우리도 모르게 데이터의 규칙성을 파악한다 하지만 컴퓨터는 인간과 다르게 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

 

 선택 정렬을 시작으로 여러 정렬 소스 코드에 대해 배워보겠습니다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

6-1. 선택 정렬 소스코드

 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬 알고리즘이라 한다.

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

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        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]

간단히 스와프에 대해 소개하겠습니다. 스와프란 두 원소의 위치를 변경하는 것으로 Python에서는 아래와 같이 간단히 구현할 수 있습니다.

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array) # [5, 3]

---

6-3. 삽입 정렬 소스코드

 삽입 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 선택 정렬에 비해 구현 난도는 높은 편이지만, 실행 시간 측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 삽입 정렬의 재미있는 특징은, 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다.

 즉, 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요가 없다.

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

# 첫 번째 원소는 정렬이 되어 있다고 가정하기 때문에 세지 않음.
for i in range(1, len(array)):
    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) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

---

6-4. 퀵 정렬 소스코드

 퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 참 들을 때마다 사고 방식이 대단하다고 느낀다.

 

 퀵 정렬에서는 피벗(pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 피벗이라 한다.

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬은 구분하는데, 이 책에서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 설명한다. 

 

 호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다. 

• 리스트에서 첫 번째 데이터를 피벗으로 정한다.

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

array = [5, 7, 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 # 9
    while left <= right : # 조건 1
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot] : # 조건2 : 조건 1이 참일 때만
            left += 1 # 조건2-1 : 1과 2 모두 참일 때
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot] : # 조건3 : 조건 1이 참이고, 조건 2의 작업이 끝나고
            right -= 1 # 조건3-1 : 조건 1과 조건 3이 참일 때

        # 조건 1이 참이고, 조건 2와 3의 작업이 끝난 후
        if left > right : # 엇갈렸다면 작은 right -= 1 데이터와 피벗을 교체
            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)

# while문이 2개니까 순간 헷갈려서 찍어보면서 이해함
#
quick_sort(array, 0, len(array)-1)
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 퀵 정렬은 정리하면서도 다시 책을 들여다볼 만큼 한 번에 이해하기는 쉽지 않았다. 하지만 한번 접했기 때문에 관련된 문제가 나올 경우 해결할 수 있을 것이다.

---

6-5. 파이썬의 장점을 살린 퀵 정렬 소스코드

array = [5, 7, 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 = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

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

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

퀵 정렬의 경우 앞의 정렬들이 시간 복잡도 O(N^2)을 띄는 것에 반해 O(NlonN)이다.
하지만 데이터가 무작위로 입력되어 있는 경우가 아닌 정렬되어 있을 경우에는 느리게 작동 함.(O(N^2))
삽입 정렬과 반대의 성질을 가짐
실제로는 최악의 경우에도 시간 복잡도가 O(NlogN)이 될 수 있게 설정되어 있으니 사용할 때는 큰 걱정하지 않아도 됨.

---

6-6. 계수 정렬 소스코드

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

'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때' 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.

 '모든 범위를 담을 수 있는 크기의 리스트를 선언'해야 하기 때문, 앞의 정렬들처럼 비교 기반의 정렬 알고리즘이 아니다.

1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고 모두 0으로 초기화시켜줌.
2. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

# 모든 원소의 값이 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개만 존재할 경우 심각한 메모리 낭비가 벌어짐. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니면, 동일한 값을 데이터가 여러 개 등장할 때 적합하다. 그래서 데이터 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

 되게 간단한 알고리즘인데 생각해보지 못했다. 알고 있었다면 코딩 테스트에서 꽤 유용했을 듯하다.

---

6-7. sorted 소스코드

 지금까지 다양한 정렬 알고리즘에 대해서 알아보았다. 우리가 알고리즘 문제를 풀 때는 앞서 다루었던 예제처럼 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만, 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 많다.

  계수 정렬 정도는 알아두면 좋을 것 같다.

 

 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.

퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 리스트, 딕셔너리 자료형들을 입력받아서, 리스트 자료형을 반환한다.

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

# 6-7.
result = sorted(array)
print(result) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

---

6-9. 정렬 라이브러리에서 ket를 활용한 소스코드

 sorted나 sort를 이용할 때는 key 매개변수를 입력으로 받을 수도 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

 예를 들어 리스트의 형태가 튜플로 구성되어 있을 때, 각 데이터의 두 번째 원소를 기준으로 설정하는 경우 다음과 같은 형태의 소스코드를 작성할 수 있다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data) :
    return data[1]

result = sorted(array, key=setting)
print(result) # [('바나나', 2), ('당근', 3), ('사과', 5)]

---

 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 효과적이다.

문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

 

 이번 Chapter는 여러 정렬 소스코드들에 대해 배워보았고, 다음 Chapter에서는 정렬 알고리즘이 코딩 테스트에 어떤 식으로 출제되는지 배워보겠습니다.

 

Chapter6(2)에서 뵙겠습니다. :)