[알고리즘] 정렬(Sorting)

정렬(Sorting)

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘을 공부하다 보면 자연스럽게 알고리즘 효율의 중요성을 깨달을 수 있다. 

 

예를 들어 숫자가 하나 씩 적힌 카드가 10장이 있다.이제 이 카드를 오름차순으로 정렬하자. 보통은 카드를 빠르게 흝고 숫자가 0부터 9까지로 구성된   걸 눈치챈 다음 카드를 0부터 9까지 순차적으로 나열할 것이다. 이러한 과정 속에서 우리의 뇌는 우리도 모르게 데이터의 규칙성을 파악한다. 하지만 우리에게 쉽다고 컴퓨터에도 쉬운 일은 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

 

이 카드 예제를 기준으로 정렬 알고리즘을 설명하겠다. 또한 여기서 다루는 예제는 모두 오름차순 정렬을 수행한다고 가정한다. 내 림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기를 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 그래서 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기하여 내림차순 리스트를 만들 수 있다. 

 

선택 정렬(Selection Sort)

Selection Sort

선택 정렬(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]

위 코드에서 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 다음처럼 간단히 리스트 내 두 원소의 위치를 변경할 수 있다.

# 파이썬 스와프(Swap) 소스코드

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

[5, 3]

 

선택 정렬의 시간 복잡도

선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 앞의 코드처럼 구현했을 때 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2로 볼 수 있다. 따라서 근사치로 N x (N + 1) / 2 번의 연산을 수행 한다고 가정하자. 이는 (N^2 + N) / 2로 표현할 수 있는데, 빅오 표기법으로 간단히 O(N^2)라고 표현할 수 있다. 

선택 정렬의 시간 복잡도는 O(N^2)이다. 직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다. 만약 정렬해야 할 데이터의 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어난다. 따라서 선택 정렬은 다른 알고리즘과 비교해 매우 비효율적이다. 다만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다. 

 

 

삽입 정렬(Insertion Sort)

Insertion Sort

삽입 정렬(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)

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

 

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었으므로 O(N^2)이다. 다만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 

 

 

퀵 정렬(Quick Sort)

Quick Sort

퀵 정렬(Quick Sort)은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로, 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 

퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 그중 가장 대표적인 분할 방식은 호어 분할(Hoare Partition) 방식이다.

호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다. 이와 같이 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

퀵 정렬 소스코드

▼ 널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드

array = [5, 7, 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]
    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]

 

▼ 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드, 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이나, 더 직관적이고 기억하기 쉽다.

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

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

 

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN)으로 앞선 두 정렬 알고리즘에 비해 매우 빠른 편이다. 다만 최악의 경우 시간 복잡도가 O(N^2)이 될 수 있다. 데이터가 무작위로 입력되는 경우 퀵은 정렬은 빠르게 동작할 확률이 높다. 하지만 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다. 

 

 

계수 정렬(Count Sort)

Count Sort

계수 정렬(Count Sort)은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘으로, 앞선 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.

계수 정렬 알고리즘은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다. 결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록되는 것이다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다.  

계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언'해야 하기 때문에 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다. 

 

계수 정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
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  # 각 데이터에 해당하는 인덱스의 값 증가

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씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 

 

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있다. 

 

 

파이썬의 정렬 라이브러리

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

 

sorted 소스코드

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]

 

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

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]

 

sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. 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. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.