Chapter 6. 정렬

정렬

개념 정리

정렬

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 예) 카드 크기에 따라 순서대로 나열하도록 하는 것

카드

특징

• 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나
• 데이터를 정렬하면 이진 탐색 (Binary Search)이 가능 (다음 챕터 내용)

정렬 알고리즘 소개

 다양한 알고리즘이 존재하지만, 이 중에 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 소개하려고 한다. 여기서는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다.

• 아래의 카드를 기준으로 정렬 알고리즘 설명 진행

섞인 카드

정렬된 카드

선택 정렬

• 매번 가장 작은 것을 선택해 앞의 데이터와 변경하여 정렬
• 알고리즘
  1. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 변경
  2. 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꿈
• 그림 설명
  1. 전체 중에서 가장 작은 수 (0)를 선택하여 맨 앞에 있는 수 (7)와 위치 변경
  2. 정렬된 첫 번째는 제외하고 가장 작은 수 (1)를 선택하여 처리되지 않은 수 중 가장 앞에 있는 수 (5)와 위치 변경
  3. 정렬되지 않는 데이터 중 가장 작은 수 (2)를 선택하여 처리되지 않은 수 중 가장 앞에 있는 수 (9)와 위치 변경
  4. 이와 같은 방식을 반복하면, 0 1 2 3 4 5 6 7 8 9가 되며 정렬을 마침
• 코드

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)

• 시간 복잡도
  • 가장 작은 수를 찾기 위한 연산 : N + (N - 1) + (N - 2) + ... + 2 = N * (N + 1) / 2
  • O(N^2)

삽입 정렬

• 특정한 데이터를 적절한 위치에 삽입
• 선택 정렬 vs 삽입 정렬
  • 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘
  • 삽입 정렬은 필요할 때만 위치를 변경, 특히 데이터가 거의 정렬되어 있을 때 훨씬 효율적
  • 선택 정렬은 현재 데이터의 상태와 관계없이 모든 원소를 비교
• 알고리즘 (삽입 정렬은 두 번째 데이터부터 시작)
  1. 두 번째 수와 첫 번째 수와 비교해 더 작다면, 위치 변경
  2. 세 번째 수와 정렬된 수(1, 2번째)와 비교해 더 작은 게 있다면, 해당하는 위치에 삽입
• 그림 설명 (삽입 정렬은 두 번째 데이터부터 시작)
  1. 두 번째 수인 5가 어떤 위치에 들어갈지 판단, 왼쪽 수 (7) 보다 작으므로 위치 변경
  2. 이어서 9가 어떤 위치에 들어갈지 판단, 왼쪽 수 (7) 보다 크므로 그대로
  3. 이어서 0이 어떤 위치에 들어갈지 판단, 왼쪽 수 (5, 7, 9) 보다 작으므로 가장 왼쪽으로 이동
  4. 이와 같은 방식을 반복하면, 0 1 2 3 4 5 6 7 8 9가 되며 정렬을 마침
• 코드

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)

• 시간 복잡도 : O(N^2)

퀵 정렬

• 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
• 피벗 (Pivot) : 큰 숫자와 작은 숫자를 교환할 때의 기준
  
  • 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬을 구분
  • 여기서는 가장 대표적인 분할 방식인 호어 분할 방식을 설명
• 알고리즘 (호어 분할)
  1. 리스트에서 첫 번째 데이터를 피벗으로 설정
  2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾음
  3. 큰 데이터와 작은 데이터의 위치를 서로 교환
• 그림 설명 (호어 분할)
  1. 리스트의 첫 번째 수 (5)를 피벗으로 설정
  2. 왼쪽부터 5보다 큰 수 선택(7), 오른쪽부터 5보다 작은 수 선택(4) -> 7과 4 위치 변경
  3. 다시 왼쪽부터 5보다 큰 수 선택(9), 오른쪽부터 5보다 작은 수 선택(2) -> 9와 2 위치 변경
  4. 다시 왼쪽부터 5보다 큰 수 선택(6), 오른쪽부터 5보다 작은 수 선택(1) -> 1과 5 위치 변경
     
     • 이때 왼쪽에서 찾은 수와 오른쪽에서 찾은 수가 서로 엇갈림
     • 엇갈린 경우에는 작은 수와 피벗의 위치를 변경
  5. 5와 1의 위치를 변경하였으므로 리스트의 첫 번째 수 (1)를 피벗으로 설정하고 다시 진행
• 특징
  • 하나의 피벗 결정 및 정렬이 완료되면, 오른쪽은 피벗보다 작은 수, 왼쪽은 피벗보다 큰 수로 나뉨
  • 왼쪽과 오른쪽을 분할하여 다시 정렬을 진행하기에 재귀적으로 구현됨

정렬 과정

• 코드

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

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

    pivot = start
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[pivot] >= array[left]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right >= start and array[pivot] <= array[right]:
            right -= 1
        if left < right: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
        else: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[pivot], array[right] = array[right], array[pivot]
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

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

• 시간 복잡도
  • 앞서 선택 정렬과 삽입 정렬에 비하면 훨씬 빠른 속도
  • 평균 시간 복잡도 : O(N logN)
  • 최악의 경우 시간 복잡도 : O(N^2)
  • 파이썬의 기본 정렬 라이브러리는 O(N logN)을 보장해 줌

계수 정렬

• 특정한 조건이 부합할 때 사용 가능하지만, 매우 빠른 정렬 알고리즘
• 특징
  
  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
  • 일반적으로 가장 작은 데이터와 큰 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
  • 비교 기반의 정렬이 아닌 별도의 리스트를 선언하고 정렬에 대한 정보를 담음
• 알고리즘
  1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 리스트 생성 후 0으로 초기화
  2. 데이터를 하나씩 확인하며, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
  3. 마지막에는 첫 번째 데이터부터 그 값만큼 인덱스를 출력
• 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 1, 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=' ')

• 시간 복잡도 : 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 시간 복잡도는 O(N + K)
• 공간 복잡도
  • 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합
  • 예) 0과 999,999 2개의 수의 정렬을 위해 크기가 100만인 리스트를 선언해야 함
  • 예) 성적의 경우 100점 맞은 학생이 여러 명일 수 있기 때문에 효과적

파이썬의 정렬 라이브러리

sorted(), sort()

• 퀵 정렬과 동작 방식이 비슷한 병합 정렬로 만들어짐
• 병합 정렬은 퀵 정렬보다는 느리지만 O(N logN)을 보장
• sorted() : 정렬된 결과를 반환
• sort() : 정렬된 결과를 반환하는 것이 아닌 내부 원소가 바로 정렬됨
• 정렬 코드

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

result = sorted(array)
print(result)

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

array.sort()
print(array)

• 키를 활용한 정렬 코드
  • key 값으로는 하나의 함수가 들어가야 하며, 이는 정렬 기준이 됨
  • 예) 리스트의 데이터가 튜플로 구성되어 있을 때, 두 번째 원소를 기준으로 정렬

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

def setting(data):
    return data[1]
    
result = sorted(array, ket=setting)
print(result)