4일차 - 정렬

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

 

본 책에서는 선택, 삽입, 퀵, 계수 정렬을 다루고, 파이썬의 정렬 라이브러리를 다룬다.

 

1. 선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는것. 가장 작은 것을 선택한다는 의미에서 선택정렬이라고 한다.

시간복잡도는 O(N^2)이다.

 

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)

 

위의 코드를 보면서 파이썬은 swap 과정이 간편하다고 생각한다.

예를 들어 arr = [1, 2]가 있다고 하면 아래와 같이 swap하면 된다.

arr = [1, 2]
arr[0], arr[1] = arr[1], arr[0]

print(arr)

 

 

2. 삽입 정렬

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는것.

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):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
print(array)

 

3. 퀵 정렬

알고리즘 과목에서 배웠던 정렬 중 하나이다.

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

퀵 정렬에서는 pivot이 사용되는데, 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'이다.

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

시간 복잡도는 O(NlogN)

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))

비교적 빠른 시간복잡도이다. 왜 이러한 시간복잡도가 나오는지는 추후 CS공부에서 작성하겠다.

 

4. 계수 정렬

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

최악의 경우에도 수행시간 O(N+K)를 보장한다.

리스트에서 각 데이터가 몇 번 등장했는데 그 횟수가 기록되는데, 그 횟수를 기반으로 출력하는 방식이다.

개인적으로 Counter와 비슷한 느낌이다.

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

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= ' ')

 

 

파이썬의 정렬 라이브러리는 sort,sorted를 사용하고, 거기의 인자인 reverse와 key를 통해 원하는 결과를 도출 할 수 있는데 도움이 된다. 이런 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.

 

이번 챕터의 예시 문제들은 정렬 라이브러리 사용에 관한 문제이기에 넘기겠다.