Skip to main content

정렬

선택 정렬​

컴퓨터가 데이터를 정렬할 때 어떻게 할지 한번 생각해보자. 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원식적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 한다.


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

# 0부터 9까지 반복
for i in range(len(array)):
  # 가장 작은 원소의 인덱스
  min_index = i
  # i의 다음 인덱스부터 끝까지 반복하면서 더 작은 값이 있을 경우 min_index에 저장
  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)

선택 정렬 시간 복잡도​

  • O(N^2)

선택 정렬은 기본 정렬 라이브러리와 다른 정렬 알고리즘과 비교하였을 때 매우 비효율적이지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.

삽입 정렬​

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?' 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 **삽입 정렬(Insertion Sort)**이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

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

for i in range(1, len(array)):
  # 인덱스 i부터 1까지 감소하며 반복 / 한 칸씩 왼쪽으로 이동
  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)

삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다. 여기서 꼭 기억할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

퀵 정렬 (Pivot + Partitioning)​

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?' 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

sort

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)

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

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

퀵 정렬 시간 복잡도​

  • 평균: O(NlogN)
  • 최악: O(N^2)

위처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작하며 앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다. 실제로 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다.

계수 정렬​

계수 정렬(Count Sort)알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 예를 들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

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

계수 정렬 시간 복잡도​

  • O(N + K)

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하고 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.

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