4. 정렬 알고리즘

hiworld·2022년 6월 19일
0
post-thumbnail

📌 1. 선택 정렬 (Selection Sort)

  • 매번 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞의 데이터와 바꾸는 것을 반복

  • 시간 복잡도

    • N개의 데이터를 정렬한다고 할 때, N개 중 최솟값 앞으로 보내기, N-1개 중 최솟값 앞으로 보내기, ..., 2개 중 최솟값 앞으로 보내기 수행

    • = N + (N - 1) + (N - 2) + ... + 2 = (N - 1)(N + 2) / 2 = (N2 + N - 2) / 2

    • O(N2)

    • 주어진 데이터가 얼마나 정렬되어 있는지 상관없이, 무조건 모든 원소를 비교하여 최솟값을 찾는 작업을 반복적으로 수행해야 함

  • 공간 복잡도

    • O(N)
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]

for i in range(len(array) - 1):
  min_idx = i
  for j in range(i+1, len(array)):
    if array[j] < array[min_idx]:
      min_idx = j

  array[i], array[min_idx] = array[min_idx], array[i]

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

📌 2. 삽입 정렬 (Insertion Sort)

  • 처리되지 않은 데이터를 하나씩 확인하며 적절한 위치에 삽입

  • 처리를 마친 앞부분의 데이터들은 무조건 정렬되어 있는 상태

  • 시간 복잡도

    • O(N2)

    • BUT 선택 정렬과 다른 점은, 주어진 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

    • 최선의 경우, 즉 모든 데이터가 이미 정렬되어 있는 상태라면, O(N)의 시간 복잡도를 가짐. B/C inner loop이 항상 break를 만나 바로 끝날 것이기 때문에 사실상 outer loop만 있는 것과 동일하기 때문.

  • 공간 복잡도

    • O(N)
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]

for i in range(1, len(array)): # 2번째 원소부터 시작하면 됨
  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]

📌 3. 퀵 정렬 (Quick Sort)

  • 기준 데이터(Pivot)를 설정(e.g., 첫 번째 데이터)하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

  • 현재 데이터의 정렬 상태와 상관없이 일반적으로 가장 많이 사용되는 정렬 알고리즘

  • 피벗을 기준으로 데이터 분할 (Divide or Partition) -> 재귀적으로 반복

  • 시간 복잡도

    • 평균적으로, O(NlogN)

      • 너비 * 높이 = N * logN
    • 최악의 경우, O(N2)

      • 이미 정렬된 배열인 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]에서 퀵 정렬을 한다고 할 때, 분할이 균등하게 이뤄지는 게 아니라 매번 편향된 분할이 이뤄짐.
  • 공간 복잡도

    • O(N)

일반적인 형태의 퀵 정렬 소스코드

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

def quick_sort(start, end): # start와 end는 idx 기준
  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: # left와 right이 엇갈렸다면, 피벗과 작은 데이터(이 경우엔 right) 교체
      array[pivot], array[right] = array[right], array[pivot]
    else:
      array[left], array[right] = array[right], array[left]

  quick_sort(start, right - 1)
  quick_sort(right + 1, end)

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

더 직관적 BUT 시간이 좀 더 걸리는 소스코드

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

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]

📌 4. 계수 정렬 (Count Sort)

  • 각각의 데이터가 몇 번씩 등장하는지를 카운트하는 방식

  • 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하지만 매우 빠르게 동작하는 정렬 알고리즘

  • 시간 복잡도 & 공간 복잡도

    • O(N + K) (N = 데이터의 개수, K = 데이터 중 최댓값)

    • 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적

    • BUT 데이터 = [0, 999999]와 같이 주어질 때는 매우 비효율적

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

count = [0] * (max(array) + 1)

for i in array:
  count[i] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end = ' ') # 0 0 0 1 2 2 3 4 5 5 6 7 8 9 9

정렬 라이브러리는 최악의 경우에도 항상 시간 복잡도 O(NlogN)을 보장한다. 따라서, 문제에서 특정 정렬 알고리즘 사용을 요구한 게 아니라면 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 제한되어 있으며 빠른 동작이 필요할 땐 계수 정렬을 사용하면 된다.

📌 파이썬의 기본 정렬 라이브러리

  • 어떤 리스트의 원소가 튜플로 이루어져 있을 때, sort()를 이용하면 기본적으로 각 튜플 안의 원소의 순서에 맞게 정렬됨. 즉, 1번째 원소 기준 -> 1번째 원소 같다면 2번째 원소 기준 -> 2번째 원소 같다면 3번째 원소 기준 -> ...
array = [(3, 1, 2), (1, 2, 4), (1, 3, 2), (5, 2, 1), (3, 1, 1)]

first_array = sorted(array)
print(first_array) # [(1, 2, 4), (1, 3, 2), (3, 1, 1), (3, 1, 2), (5, 2, 1)]

second_array = sorted(array, reverse = True)
print(second_array) # [(5, 2, 1), (3, 1, 2), (3, 1, 1), (1, 3, 2), (1, 2, 4)]

[참고]

profile
바쁘게 살아 보자!

0개의 댓글