📔 이.코.테 Part2. 정렬(Sort) 알고리즘 정리노트

Ch06. 정렬 알고리즘(Sort)

본 포스팅은 나동빈 저자의 '이것이 취업을 위한 코딩테스트다'를 공부하며 정리한 노트입니다.

정렬(Sort)이란

• 데이터를 특정 기준에 따라 순서대로 나열하는 것을 말한다
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다

✅ 굉장히 다양한 문제 상황에서 적절한 정렬 알고리즘을 사용하는 것이 중요하다

 

• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 계수 정렬(Count Sort)
• 파이썬 정렬 라이브러리(Sort Library)

1. Selection Sort

# Selection Sort 
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[j] < array[min_index]:
        	min_index = j # 처리되지 않은 데이터 중에서 가장 작은 데이터를 찾는다 
    array[i], array[min_index] = array[min_index], array[i] # SWAP 스와핑

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

 

2. Insertion Sort

처리되지 않은 데이터를 하나씩 선택해 적절한 위치에 삽입하자

 

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)

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

 

3. Quick Sort

a.k.a 빠른 정렬 알고리즘

기준이 되는 데이터를 설정하고(Pivot) 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?

• 책에서는 호어 분할(Hoare Partition) 방식으로 퀵 정렬을 설명한다
• Hoare Partition에서는 리스트의 첫 번째 데이터를 피벗으로 정한다
• 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그리고 큰 데이터와 작은 데이터의 위치를 서로 변경해준다
• 이러한 과정을 반복하면 '피벗'에 대한 정렬이 수행된다

# 6-4.py 퀵 정렬 소스코드

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

def quick_sort(array, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        return
    pivot = start  # Hoare Partition에서는 리스트의 첫 번째 데이터를 피벗으로 한다
    left = start + 1
    right = end
    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)

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

 

• 코드 리뷰

  • 피벗을 정해주고 피벗을 기준으로 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽부터 피벗보다 작은 데이터를 찾는다

  • 왼쪽과 오른쪽에서 피벗쪽으로 이동을 하며 찾은 데이터 중 피벗보다 큰 데이터와 피벗보다 작은 데이터를 교환한다. 이 때 찾는 값의 위치가 엇갈린 경우에는 작은 데이터와 피벗의 위치를 서로 변경해준다

  • 분할 이후에는 피벗을 기준으로 왼쪽과 오른쪽 부분에서 각각 정렬을 수행한다

    (그러면 분할된 영역을 각각 정렬해 줄 것이다)

✅ 코드를 이해하기 위해 노력하자. 그리고 다시 한번 구현해보자!

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

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:]  # tail: 피벗을 제외한 리스트

    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]

 

4. Count Sort

• 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다
• 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다
• 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다
• 계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다
• 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

✅ 소스 코드를 통해 이해해보도록 하자

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

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)  # 0을 포함해서 선언. e.g. 0, 1, 2, ..., 9

for elem in array:  # 리스트 전체를 반복하며 카운트 하겠죠?
    count[elem] += 1

# Do-it
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씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최대값의 크기만큼 반복을 수행해야 하기 때문이다
• 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다
• 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다

계수 정렬의 공간 복잡도

• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다
• 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을 때, 계수 정렬을 고려해보자

 

파이썬의 정렬 라이브러리

# 6-7.py
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

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

 

정렬 알고리즘 문제는 어느정도 답이 정해져 있는 문제이다. 미리 만들어진 라이브러리를 이용해 효과적으로 문제를 해결할 수 있다

• 파이썬은 기본 정렬 라이브러리인sorted() 함수를 제공한다
• sorted는 병합 정렬을 기반으로 한다. 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도O(NlogN)을 보장한다는 특징이 있다
• 이러한 sorted()함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다
• 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다

# 6-8.py sort 소스코드

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

array.sort()
print(array)

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

 

• 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다
• 리스트 객체의 내장 함수인 sort()를 이용하는 것이다
• 이때는 별도의 정렬된 리스트를 반환하지 않고 내부 원소가 바로 정렬된

# 6-9.py 정렬 라이브러리에서 key를 활용한 소스코드
array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

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

정렬 라이브러리의 시간 복잡도

• 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다
• 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱 효과적이다

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

1. 정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠르 정렬이 필요한 문제: 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다

 

✅ 소스코드는 Github repository에서 살펴보실 수 있습니다

Steve-YJ/Python-Algorithm