정렬(sorting)은 데이터를 특정 기준으로 순서대로 나열하는 것이다. 정렬 알고리즘은 가장 많이 사용되는 알고리즘 중 하나로 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.

1. 선택 정렬 (Selection Sort)

선택정렬은 매번 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다.

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 (N-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]

시간 복잡도: $O(N^{2})$

선택 정렬은 가장 작은 데이터를 찾아서 앞으로 보내는 것을 (N-1)번 수행한다고 했다. 가장 작은 데이터를 찾기 위해서 비교 연산은 각 step마다 $N + (N-1) + (N-2) + (N-3) + … + 2 \approx (N^{2}+N)/2$ 로 표현할 수 있다. 반복문이 얼마나 중첩되었는지를 기준으로 시간 복잡도를 판단할 수 있다고 했고, 간단히 2중 반복문이 사용되었기 때문에 O(N^{2})으로 생각해도 된다.

선택 정렬은 기본 정렬 라이브러리를 포함한 다른 정렬 알고리즘보다 느리다.

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 데이터를 앞에서 부터 하나씩 확인하여 그 데이터를 적잘한 위치에 삽입한다. 삽입 정렬은 현재 step에서 확인하고 있는 데이터의 앞쪽은 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입한다. 따라서 첫 번째 데이터는 그 자체로 정렬되어 있다고 가정하고 두번째 데이터부터 확인한다. 적절한 위치를 찾는 방법은 바로 왼쪽에 있는 데이터와 비교한다.

삽입정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 특징이 있다. 그림을 보면 선택 정렬과 다르게 하늘색으로 칠해진 숫자들은 어떤 단계든지 항상 정렬된 상태이다. 이 때문에 현재 데이터를 삽입할 위치를 선정할 때 왼쪽으로 한 칸씩 이동하며 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 다시말해 앞쪽 데이터들을 이미 정렬된 상태이기 때문에 더 이상 데이터를 살펴볼 필요가 없는 것이다.

이처럼 삽입 정렬은 현재의 데이터를 적절한 위치에 넣는 과정을 (N-1)번 반복하면 된다. 삽입 정렬은 다음과 같이 이중반복문으로 구현하면 된다.

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-1] > array[j]:  # 바로 왼쪽 원소보다 작으면 왼쪽으로 한 칸 이동
      array[j], array[j-1] = array[j-1], array[j]
    else:  # 바로 왼쪽 원소보다 크면 종료
      break
      
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도: $O(N^{2})$ (최소 O(N))

삽입 정렬도 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었기 때문에 $O(N^{2})$만큼의 시간이 소요된다. 하지만 만약 원본 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여 O(N)의 시간 복잡도를 가진다. 보통은 삽입 정렬이 비효율적이지만 정렬이 거의 되어 있는 상황에서는 퀵 정렬 보다 강력하다.

3. 퀵 정렬

퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬은 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼 후에 리스트를 반으로 나누는 방식이다.

여기서는 pivot을 리스트의 첫 번째 데이터로 한다. Pivot을 설정하면 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 다음으로 찾은 큰 데이터와 작은 데이터의 위치를 서로 교환한다. 만약 화살표가 엇갈리면 피벗과 작은 데이터를 교환하여 분할을 수행한다. 분할된 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 다시 퀵 정렬을 수행한다. 퀵 정렬의 종료조건은 현재의 리스트의 데이터 개수가 1개인 경우이다.

퀵 정렬은 다음과 같이 재귀함수 형태로 작성한다.

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

def quicksort(array, start, end):  # start는 array의 첫번째 원소의 인덱스, end는 마지막 원소의 인덱스
  # 원소가 한개인 경우 종료
  if start >= end:
    return
  pivot = start  # 리스트의 가장 첫번째 원소를 피벗으로 설정
  left = start + 1
  right = end
  
  while left <= right:
    # 왼쪽부터 피벗보다 큰 데이터를 찾을때 까지 반복
    while (left <= end and array[left] <= array[pivot]):
      left += 1
    # 오른쪽부터 피벗보다 작은 데이터를 찾을때까지 반복
    while (start <= right and array[right] >= array[pivot]):
      right -= 1
    # 엇갈렸다면 피벗과 작은 데이터를 교체
    if left >= right:
      array[right], array[pivot] = array[pivot], array[right]
    # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체  
    else:
      array[right], array[left] = array[left], array[right]
    # 분할 이후 왼쪽과 오른쪽에서 각각 퀵 정렬 다시 수행
    quicksort(array, start, right-1)
    quicksort(array, right+1, end)
    
quicksort(array, 0, len(array)-1)
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도: O(NlogN) (최악 $O(N^{2})$)

만약 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 수행횟수는 logN이 된다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작하지만 위에서 처럼 피벗값을 리스트의 가장 첫번째 원소로 했을 때 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

4. 계수 정렬 (Count Sort)

계수 정렬은 정수 형태로 표현된 데이터가 주어지는 경우에만 적용할 수 있는 매우 빠른 알고리즘이다. 실수형 데이터는 무한한 범위를 가지기 때문에 계수 정렬을 사용하기 어렵다. 또한, 계수 정렬은 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크지 않아야 사용가능하다. 모든 데이터를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다. 계수 정렬은 앞서 다루었던 정렬 알고리즘처럼 데이터의 값을 비교하여 위치를 변경하며 정렬하는 비교 기반의 정렬 알고리즘이 아니다.

계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성하고 모든 데이터를 0으로 초기화 한다. 다음으로 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 리스트 상 데이터를 1씩 증가시키면 된다.

결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 리스트의 첫번째 데이터부터 그 값만큼 인덱스를 출력하면 된다.

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  # array[i]는 데이터
  
# 리스트에 기록된 정렬 정보 확인
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 

시간 복잡도: O(N+K)

데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 하자. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시키고, 나중에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문에 O(N+K)의 시간 복잡도를 가진다.

공간 복잡도: O(N+K)

계수 정렬은 때로 비효율적이다. 예를 들어 0과 999,999 두 개의 데이터만 존재한다고 할때 이때에도 100만길이의 리스트를 만들어야 한다. 따라서 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. ex) 성적.

5. 파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 병합 정렬을 기반으로 만들어졌는데, 보통 병합 정렬은 퀵 정렬보다 느리지만 최악의 경우에도 시간복잡도 O(NlogN)을 보장한다.

sorted()함수는 정렬된 새로운 리스트를 만들어준다. 아래와 같이 원래 a라는 배열은 유지되는 것을 볼 수 있다.

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

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

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

sort() 함수를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

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

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

sorted()나 sort()함수는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 예를 들어 튜플의 두 번째 원소를 기준으로 정렬할 수 있다.

a = [('바나나', 2), ('사과', 4), ('당근', 3)]

result = sorted(a, key = lambda x : (x[1]) )
print(result)

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

정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)을 보장한다. 따라서 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할때는 계수 정렬을 사용하고, 일반적인 상황에서는 기본 정렬 라이브러리를 사용하면 된다.