[Sorting] 기준에 따라 데이터를 정렬

정렬 알고리즘 개요

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다.

선택 정렬

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이와 같은 방법은 매번 ‘가장 작은 것을 선택’한다는 의미이서 선택 정렬(Selection Sort) 알고리즘이라고 한다.
정렬 알고리즘에서는 흔히 데이터의 개수를 N이라고 표현한다. 아래 예시에서 회색은 ‘현재 정렬되지 않은 데이터 중 가장 작은 데이터’를 의미하고 하늘색은 ‘이미 정렬된 데이터’를 의미한다.

선택 정렬 그림 설명

step 0 : 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 ‘0’을 선택해 맨 앞에 있는 데이터 ‘7’과 바꾼다.

step 1 : 이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 ‘1’을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 ‘5’와 바꾼다.

step 2 : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 ‘2’를 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 ‘9’와 바꾼다.

step 3 : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 ‘3’을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 ‘7’과 바꾼다.

중략

step 8

step 9 : 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서 정렬을 마칠 수 있다.

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

print(array)

선택 정렬의 시간 복잡도

선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 대략적으로 연산을 했을 경우 N * (N - 1) / 2 번의 연산을 수행한다고 하면 시간 복잡도는 O(N^2)이다.

삽입 정렬

삽입 정렬은 필요할 경우에만 위치를 바꾸므로 ‘데이터가 거의 정렬 되어 있을 때’ 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면에 삽입 정렬은 그렇지 않다.
삽입 정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부른다. 그리고, 삽입 정렬은 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 즉, 정렬되어 있는 데이터 리스트의 적잘한 위치를 찾은 다음, 그 위치에 삽입 된다는 것이 특징이다.

삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

아래의 과정을 통해 이해해보자!

step 0 : 첫 번째 데이터 ‘7’은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단한다. ‘7’의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 우리는 카드를 오름차순으로 정렬하고자 하므로 ‘7’의 왼쪽에 삽입한다.

step 1 : 이어서 ‘9’가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 ‘9’는 ‘5’와 ‘7’보다 크기 때문에 원래 그자리에 둔다.

step 2 : 이어서 ‘0’이 어떤 위치에 들어갈지 판단한다. ‘0’은 ‘5’, ‘7’, ‘9’와 비교했을 때 가장 작기 때문에 첫번째 위치에 삽입한다.

step 3 : 이어서 ‘3’이 어떤 위치에 들어갈지 판단한다. ‘0’과 ‘5’사이에 삽입한다.

중략

step 7

step 8

step 9 : 이와 같이 적절한 위치에 삽입하는 과정을 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): # 인덱스 i부터 1까지 감소하며 반복하는 문법
    if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
      array[j], array[j - 1] = array[j - 1], array[j]
    else:
      break
print(array)

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었기 때문이다. 중요한 점은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 것이다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 보통은 삽입 정렬이 비효율적이나 정렬이 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다 그러므로 거의 정렬이 되어있는 상태로 입력이 주어지면 다른 정렬 알고리즘보다 삽입 정렬을 사용하는게 정답률을 높힐 수 있다.

퀵 정렬

퀵 정렬이 선택 정렬, 삽입 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이다. 퀵 정렬만큼 빠른 병합 정렬 알고리즘이 있는데 추후에 한번 공부해보도록 하자. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ‘기준’을 바로 Pivot이라고 표현한다. Pivot을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 아래 설명에는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 퀵 정렬을 진행하였다.

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

파트 1

step 0 : 리스트의 첫 번째 데이터를 Pivot으로 설정하므로 Pivot은 ‘5’이다. 이후에 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택되고, 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

step 1 : 그다음 다시 Pivot보다 큰 데이터와 작은 데이터을 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 ‘9’와 ‘2’가 선택되었으므로 이 두 데이터의 위치를 서로 변경한다.

step 2 : 그다음 다시 Pivot보다 큰 데이터와 작은 데이터를 찾는다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 ‘작은 데이터’와 ‘Pivot’의 위치를 서로 변경한다. 즉, 작은 데이터인 ‘1’과 Pivot인 ‘5’의 위치를 서로 변경하여 분할을 수행한다.

step 3 분할 완료 : 이와 같이 Pivot이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자. 이제 ‘5’의 왼쪽에 있는 데이터는 모두 ‘5’보다 작고, 오른쪽에 있는 데이터는 모두 ‘5’보다 크다는 특징이 있다. 이렇게 Pivot의 왼쪽에는 Pivot보다 작은 데이터가 위치하고, Pivot의 오른쪽에는 Pivot보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트 각각에서 Pivot을 설정해서 동일한 방식으로 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

파트 2

왼쪽 리스트에서는 다음과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

파트 3

오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다. 재귀 함수와 원리가 같다면 종료 조건이 필요한데 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우이다.

아래 코드는 전통적인 퀵 정렬 소스코드이다.

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

def quick_sort(array, start, end):
  if start >= end: # 원소가 1개인 경우 종료
    return
  pivot = start # Pivot은 첫 번째 원소
  left = start + 1
  right = end
  while left <= right:
    # Pivot보다 큰 데이터를 찾을 때가지 반복
    while left <= end and array[left] <= array[pivot]:
      left += 1
    # Pivot보다 작은 데이터를 찾을 때까지 반복
    while right > start and array[right] >= array[pivot]:
      right -= 1
    if left > right: # 엇갈렸다면 작은 데이터와 Pivot을 교체
      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)

아래 코드는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드이다. 시간 면에서는 비효율적이지만 직관적이고 기억하기 쉽다.

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

def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  if len(array) <= 1:
    return array

  pivot = array[0] # Pivot은 첫 번째 원소
  tail = array[1:] # Pivot을 제외한 리스트

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

퀵 정렬의 시간 복잡도

선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N^2)을 보장한다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다. 하지만 최악의 경우 시간 복잡도는 O(N^2)이라는 것이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높지만 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

계수 정렬

계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수 정렬은 최악의 경우에도 수행 시간 O(N + K)를 보장한다. 다만, 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문이다.
계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 아래 예시에서는 가장 큰 데이터가 ‘9’이고 가장 작은 데이터가 ‘0’이다. 따라서 우리가 정렬한 데이터의 범위는 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다.
즉, 크기가 10인 리스트를 선언하면 된다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화한다.
그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

stop 0 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

stop 1 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

stop 2 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

stop 3 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

과정 반복

stop 14 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

stop 15 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다. 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.

아래는 파이썬으로 구현한 소스코드이다.

# 모든 원소의 값이 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 = '') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 시간 복잡도

데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다고 볼 수 있다.

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999. 단 2개만 존재한다고 가정하면 이럴 경우에도 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니다. 반면에 퀵 정렬은 일반적인 경우에도 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

파이썬의 정렬 라이브러리

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

sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

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

result = sorted(array)
print(result)

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

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

array.sort()
print(array)

또한, sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

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

def setting(data):
  return data[1]

resulted = sorted(array, key=setting)
print(result)

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)을 보장한다.
코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

• 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
• 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
• 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 들의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 구조적인 개선을 거쳐야 풀 수 있다.

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Algorithm 카테고리 내 다른 글 보러가기