[Algorithm] Sorting - 버블, 선택, 삽입, 병합, 퀵 정렬 (Python)

정렬

데이터를 특정한 기준에 따라 순서대로 나열

 

Bubble Sort

• 인접한 두 데이터를 비교하여 작은 데이터는 앞쪽, 큰 데이터는 뒤쪽으로 보낸다. (swap)
• 앞에서부터 시작하여 맨 뒤에 가장 큰 값을 보내고 두 번째로 큰 값을 뒤에서 두 번째로 보내는 과정을 반복하여 정렬한다.
• \(O(N^2)\)의 시간 복잡도를 갖는다. 최선의 경우에는 시간 복잡도를 \(O(N)\)까지 줄일 수 있다.

def bubble_sort(arr):
  for i in range(len(arr) - 1):
    for j in range(len(arr) - 1 - i):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
  return arr

 

Selection Sort

• 가장 작은 데이터를 선택하여 맨 앞의 데이터와 교환하는 과정을 반복하여 정렬한다.
• \(O(N^2)\)의 시간 복잡도를 갖는다.

def selection_sort(arr):
  for i in range(len(arr)):
    min_index = i
    for j in range(i + 1, len(arr)):
      if arr[j] < arr[min_index]:
        min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr

 

Insertion Sort

• 특정한 데이터를 적절한 위치에 삽입한다.
• 삽입하고자 하는 특정 데이터 앞까지의 데이터들은 이미 정렬된 상태라고 가정하고 정렬된 데이터들 사이에서 적절한 위치를 찾아 해당 위치에 삽입한다.
• \(O(N^2)\)의 일정한 시간 복잡도를 갖는다.
• 리스트의 데이터가 거의 정렬되어 있는 상태라면 빠르게 동작해 최선의 경우 \(O(N)\)의 시간 복잡도를 갖는다.

def insertions_sort(arr):
  for i in range(1, len(arr)):
    for j in range(i, 0, -1):
      if arr[j] < arr[j - 1]:
        arr[j], arr[j - 1] = arr[j - 1], arr[j]
      else:
        break
  return arr

 

Merge Sort

• 분할 정복과 재귀를 이용한 알고리즘
• 리스트를 각 원소가 1개가 될 때까지 left, right로 절반씩 나눈 후 left와 right의 원소를 비교해 가며 정렬한다.
• \(O(NlogN)\)의 시간 복잡도를 갖는다.

def merge(left, right):
  i, j = 0, 0
  # 정렬된 데이터를 담을 리스트
  sorted_arr = []

  # left와 right를 오름차순으로 정렬
  while i < len(left) and j < len(right):
    if left[i] < right[j]:
      sorted_arr.append(left[i])
      i += 1
    else:
      sorted_arr.append(right[j])
      j += 1

  # left 혹은 right에 남아있는 원소들 모두 담기
  while i < len(left):
    sorted_arr.append(left[i])
    i += 1
  while j < len(right[j]):
    sorted_arr.append(right[j])
    j += 1

  # 정렬된 리스트 리턴
  return sorted_arr

def merge_sort(arr):
  # arr의 원소가 하나라면 그대로 리턴
  if len(arr) <= 1:
    return arr

  # left와 right로 나누어 재귀호출을 통한 정렬
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])

  # left와 right 합치기
  return merge(left, right)

 

Quick Sort

• 기준이 되는 pivot 값을 정한 후 pivot을 기준으로 분할, 정렬한다.
• Merge sort가 left와 right를 균등하게 분할하였다면 퀵정렬은 pivot을 정하고 해당 위치를 기준으로 분할한다.
• 추가적인 메모리 공간이 필요 없다.
• 평균적으로 \(O(NlogN)\)의 시간복잡도를 갖지만, 최악의 경우 (데이터가 이미 정렬되어 있는 경우) \(O(N^2)\)의 시간 복잡도를 갖는다.
• 이러한 단점을 보완하기 위해 최악의 경우에도 \(O(NlogN)\)의 시간 복잡도를 보장할 수 있도록 pivot 값을 중간이나 랜덤 값으로 잡는 등 추가적인 로직을 더해준다.

def quick_sort(arr):
  if len(arr) <= 1:
    return arr

  pivot = arr[0]
  tail = arr[1:]

  left = [x for x in tail if x <= pivot]
  right = [x for x in tail if x > pivot]
  return quick_sort(left) + [pivot] + quick_sort(right)

 

Count Sort

• 특정한 조건이 부합할 경우에만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 데이터의 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하다.
• Count sort는 일반적으로 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 포함된 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
• 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때 Count sort의 시간 복잡도는 \(O(N + K)\)이다.

 

Python의 정렬 라이브러리

• 파이썬은 기본 정렬 라이브러리 sorted() 함수를 제공한다.
• 리스트 객체의 내장 함수인 sort()를 사용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소를 바로 정렬할 수 있다.
• 파이썬의 정렬 라이브러리는 항상 최악의 경우에도 \(O(NlogN)\)의 시간 복잡도를 보장한다.