📌 강의 바로가기

개념과 코드, 이미지는 해당 책과 강의를 참고하였습니다.

정렬(Sorting)

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

일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처러럼 사용됩니다.

여러 개의 데이터(카드)를 어떻게 정렬할까요? 눈으로 봤을 때는 0부터 9까지의 숫자가 있는 것 같아서 순서대로 정렬해주고 싶습니다.

컴퓨터는 알고리즘을 활용하여 어떻게 정렬을 할 수 있을까요?

1. 선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

• 정렬할 데이터를 준비합니다.

• 가장 작은 데이터 0을 7과 바꿔줍니다.

• 0이 정렬되었습니다.
• 가장 작은 데이터 1과 5의 위치를 바꿔줍니다.

• 0 다음으로 1이 정렬되었습니다.
• 가장 작은 데이터 2와 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)):
        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]

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보냅니다.

전체 연산 횟수는

$N + (N-1) + (N-2) + ... + 2$

입니다.

이는 ($N^2+N-2)/2$

2. 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.

선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.

• 첫 번째 데이터 7은 그 자체로 정렬이 되어 있다고 판단합니다. 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재합니다.

기본적으로 오름차순 정렬을 생각한다면 여기서는 5의 원소가 7보다 작다면 왼쪽으로 크다면 오른쪽으로 삽입되어야 합니다.

• 두 번째 데이터 9는 7보다 크기 때문에 그자리에 그대로 남습니다.

• 그다음 데이터는 0입니다. 0은 9보다 작고, 7보다 작고, 5보다도 작기 때문에 매번 위치를 옮겨서 맨 앞으로 이동하게 됩니다.

• 그다음 3은 어디로 들어가게 될까요?

9보다 작고, 7보다 작고, 5보다 작으니 데이터의 왼쪽으로 이동하고, 0보다 크기 때문에 오른쪽에 위치하게 됩니다.

이 과정을 반복하는 것이 삽입 정렬입니다. 똑같이 코드로 구현해보겠습니다.

삽입 정렬 소스코드

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[i]
        else: # 자기보다 더 작은 데이터를 만나면 그 위치에서 멈춤
            break
        
print(array)

# 실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도는 $O(N^2)$입니다.

선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.

삽입 정렬은현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.

• 최선의 경우 $O(N)$의 시간 복잡도를 가짐
• 이미 정렬되어 있는 상태에서 삽입 정렬을 수행하면?

이미 0부터 9까지의 데이터가 다 정렬되어 있을 때, 삽입 정렬은 어떻게 수행이 될까요?

0과 1을 비교하고, 2를 비교하고 ... 각 원소가 들어갈 위치를 정하는데 이미 정렬되어 있어서 탐색 과정이 바로 멈춰지기 때문에 단순히 상수 시간으로 시간 복잡도가 $O(N)$이 됩니다.

3. 퀵 정렬

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

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나입니다.

병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘입니다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정합니다.

퀵 정렬 동작 예시

• 현재 기준이 되는 피벗의 값은 5입니다. 왼쪽에서부턴 5보다 큰 데이터를 선택하고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4를 선택합니다.

• 이제 선택한 두 데이터를 서로 변경합니다.

• 마찬가지로 피벗을 기준으로 더 큰 데이터 9, 작은 데이터 2를 선택하고 서로 위치를 바꿔줍니다.

• 이번 경우는 큰 데이터 6과 작은 데이터 1의 위치가 엇갈린 경우입니다. 이처럼 위치가 엇갈리는 경우에는 '피벗'과 '작은 데이터'의 위치를 서로 변경합니다.

• 분할이 완료되었습니다.

• 피벗을 기준으로 오른쪽에 있는 데이터는 모두 5보다 크고 왼쪽의 데이터는 5보다 작습니다.

• 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 합니다.

• 왼쪽 데이터 묶음 정렬: 왼쪽에 있는 데이터에 대해 마찬가지로 정렬을 수행합니다.

• 오른쪽 데이터 묶음 정렬: 오른족에 있는 데이터에 대해 마찬가지로 정렬을 수행합니다.

이 과정을 반복하면 전체 데이터에 대해 정렬이 수행됩니다.

이제 퀵 정렬이 빠른 이유에 대해 직관적으로 이해해봅시다.

이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 $O(NlogN)$를 기대할 수 있습니다.

• 너비 X 높이 = $N$ X $log N = NlogN$

퀵 정렬은 평균의 경우 $O(NlogN)$의 시간 복잡도를 가집니다.

하지만 최악의 경우 $O(N^2)$의 시간 복잡도를 가집니다.

첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에서 퀵 정렬을 수행한다면 어떻게 될까요?

첫 번째 피벗으로 0을 설정한다면, 왼쪽에서부터 큰 데이터를 찾으면 1이 되고 오른쪽으로부터 작은 데이터를 찾는데 작은 값이 없기 때문에 자기 0을 선택하게 됩니다. 그래서 0과 0의 자리가 바뀌는 불필요한 분할이 이루어집니다.

두 번째 원소 1로 넘어가도 똑같겠죠.

그래서 최악의 경우 분할이 수행되는 횟수가 매번 선형 탐색을 수행해야 되기 때문에 전체 시간 복잡도가 $O(N^2)$이 됩니다.

# 퀵 정렬 소스코드

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[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]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    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]

4. 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘입니다.

계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능합니다.

데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 $O(N+K)$

계수 정렬 동작 예시

가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성합니다.

• 정렬할 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

• 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킵니다.

예를 들어, 가장 앞에 있는 7은 인덱스 7에 값을 1 증가 시킵니다.

이런식으로 정렬된 데이터를 순서에 맞게 하나씩 정렬시키면 아래와 같습니다.

최종적으로 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록됩니다.

결과 확인시, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력합니다.

• 출력 결과: 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

# 계수 정렬

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

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

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
    print(count)
    
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

5. 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    # 1부터 100 사이의 랜덤한 정수
    array.append(randint(1,100))
    
# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스 코드
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]
    
# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("선택 정렬 성능 측정:", end_time - start_time)

# -------------------------------------------------
# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    # 1부터 100 사이의 랜덤한 정수
    array.append(randint(1, 100))
    
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

# 측정 종료
end_time = time.time()
# 수행 시간 출력
print("기본 정렬 라이브러리 성능 측정:", end_time-start_time)

선택 정렬 성능 측정: 4.591437816619873
기본 정렬 라이브러리 성능 측정: 0.0009920597076416016

수행 시간을 비교해보면 선택 정렬 알고리즘을 소스 코드로 구현한 것보다 파이썬에 내장되어 있는 sort를 사용했을 때 시간이 매우 단축된다는 사실을 알 수 있습니다!👏

6. 정리

정렬에서 다룬 네 가지 정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬입니다.

추가적으로 표준 정렬 라이브러리는 최악의 경우에도 $O(NlogN)$을 보장하도록 설계되어 있습니다.