정렬 알고리즘

1. 시간 복잡도

먼저, 정렬의 성능과 관련된 시간 복잡도에 대해 알아보겠습니다.

1-1. 시간 복잡도

시간 복잡도란, 코드의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도입니다.

시간 복잡도의 점근 표기법으로는 3가지가 있습니다.

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

이 중에서 알고리즘의 시간 복잡도를 측정할 때, 주로 빅오(Big-O) 표기법을 사용합니다.

이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이며, 입력값의 크기가 증가할 때 표기법을 보고 어떻게 증가하는지 파악할 수 있습니다.

 

1-2. Big-O 표기법

https://www.hackerearth.com/practice/notes/big-o-cheatsheet-series-data-structures-and-algorithms-with-thier-complexities-1/

 

 

① O(1) - 상수 시간 복잡도

    · 입력 크기에 관계없이 일정한 시간 안에 실행됩니다.

    ex) 인덱스를 통한 배열의 요소 접근, stack의 push·pop

 

② O(n) - 선형 시간 복잡도

    · 실행시간이 입력크기에 따라 선형적으로 증가합니다.

    ex) 정렬되지 않은 배열에서의 선형 검색, 1중 for문

 

③ O(log n) - 로그 시간 복잡도

    · 실행시간이 입력 크기에 따라 대수적으로 증가합니다.

    ex) 정렬된 배열에서의 이진 검색, binary search 알고리즘

 

④ O(n log n) - 선형 시간 복잡도

    · 실행시간이 입력 크기에 따라 n x log n만큼 증가합니다.

    ex) 퀵 정렬, 병합 정렬, 힙 정렬

 

⑤ O(n²) - 2차 시간 복잡도

    · 실행시간이 입력 크기에 따라 2차적으로 증가합니다.

    ex) 입력을 반복하는 중첩 루프, 삽입정렬, 거품정렬, 선택정렬

 

⑥ O(2ⁿ) - 지수 시간 복잡도

    · 실행시간이 입력 크기에 따라 기하급수적으로 증가합니다.

    ex) 모든 가능한 조합을 시도하는 무차별 대입 알고리즘, 피보나치수열

 

⑦ O(n!) - 팩토리얼 시간 복잡도

    · 실행시간이 입력 크기에 따라 팩토리얼적으로 증가합니다.

    ex) 집합의 모든 순열을 생성하는 알고리즘

 

---

 

2. 정렬 알고리즘

2-1. Stable과 In-place

· Stable 정렬

   정렬했을 때 중복된 값들의 순서가 변하지 않는 것을 말합니다.

   arr = [ 1, 3(1), 3(2), 7, 5, 4 ]를 정렬했을 때,

     - arr = [ 1, 3(1), 3(2), 4, 5, 7 ] ⇒ Stable( 안정 )

     - arr = [ 1, 3(2), 3(1), 4, 5, 7 ] ⇒ Unstable( 불안정 )

 

· In-place 정렬

   정렬하는데 추가적인 메모리 공간이 거의 들지 않는 것을 말합니다.

---

2-2. Bubble Sort ( 거품 정렬 )

출처 : https://east-star.tistory.com/10

  - 마치 물속에서 올라오는 물방울과 같다고 하여, Bubble Sort라는 이름이 붙여졌습니다. 

  - 거품 정렬은 첫 번째 원소부터 인접한 원소끼리 비교하며 자리를 바꾸면서, 맨 끝부터 정렬하는 방식입니다. 

  - n번째 원소와 n+1번째 원소의 값을 비교하고, n+1째의 값이 더 크다면 둘의 자리를 바꿉니다. 이를 반복하여 가장 끝부터 큰 수가 쌓이도록 하는 정렬입니다.

# Bubble Sort (python)

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

 

① 장점

• 코드가 직관적이며 구현이 간단합니다.
• Stable 정렬과 In-place 정렬에 해당합니다.

② 단점

• 데이터를 하나씩 비교하기 때문에 시간 복잡도가 최선, 평균, 최악이 모두 O(n²)이며 굉장히 비효율적입니다.
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않습니다.

③ 개선된 Bubble Sort

" 칵테일 셰이커 ( Cocktail Shaker ) 정렬" - 양방향 버블 정렬

  - Bubble Sort가 한 방향으로 정렬하는 방식이라면, 칵테일 셰이커는 최댓값, 최솟값이 배열 가장자리에 위치하여 왕복하는 정렬이다.

  - 정렬되는 동작이 칵테일 셰이커를 흔드는 것과 비슷하다고 하여 이름이 붙여졌다.

def Cocktail(arr):
  a, b = 0, len(arr)-1 # 시작, 끝
  direction = True # 방향 변환
  swap = True # 
  
  while swap:
    swap = False
    
    # 정방향
    if direction:
      for i in range(a, b):
        if arr[i] > arr[i + 1]:
          arr[i], arr[i + 1] = arr[i + 1], arr[i]
          swap = True # 목표값 발견
      b = b - 1
      direction = False # 방향 전환   
    
    # 역방향
    else:
      for i in range(b-1, a-1, -1):
        if arr[i] > arr[i + 1]:
          arr[i], arr[i + 1] = arr[i + 1], arr[i]
          swap = True # 목표값 발견
      a = a + 1
      direction = True # 방향 전환

---

2-3. Selection Sort ( 선택 정렬 )

출처 : https://east-star.tistory.com/10

  - 거품 정렬과 반대로 앞 쪽부터 정렬합니다

  - 정렬하고자 하는 범위에서 가장 작은 최솟값을 찾아 맨 앞의 값과 위치를 바꾸면서 정렬합니다.

  - 가장 작은 값을 찾았다면, 맨 앞을 제외한 배열을 다시 정렬합니다.

 

  - 비교 횟수는 많지만 실제로 값을 옮기는 횟수는 적다는 특징을 가지고 있습니다. 

  - 배열의 최솟값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌습니다.

def SelectionSort(arr):
  n = len(arr)
  for i in range(n-1):
    minIdx = i
    
    # 최솟값 위치 찾기
    for j in range(i+1, n):
      if arr[j] < arr[minIdx]:
        minIdx = j
    
    arr[i], arr[minIdx] = arr[minIdx], arr[i]

 

① 장점

• 코드가 직관적이며 구현이 간단합니다.
• In-place 정렬에 해당합니다.

② 단점

• 데이터를 하나씩 비교하기 때문에 시간 복잡도가 최선, 평균, 최악이 모두 O(n²)이며 굉장히 비효율적입니다.
• 구현하는 방식에 따라 Unstable 정렬 형태를 가질 수 있습니다.
• 새로운 데이터 추가 시 정렬 효율이 좋지 않습니다. ( 비교 횟수가 많다 보니 )

---

2-4. Insertion Sort ( 삽입 정렬 )

출처 : https://east-star.tistory.com/10

  - 거품 정렬의 비효율성을 개선하기 위해 등장한 방법입니다.

  - 모든 요소를 앞에서부터 차례대로 이미 정렬이 된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬입니다.

  - 버블 정렬보다 비교 및 교환 횟수가 적습니다.

def InsertionSort(arr):
  n = len(arr)
  for end in range(1, n):
    for i in range(end, 0, -1):
      if arr[i - 1] > arr[i]:
        arr[i - 1], arr[i] = arr[i], arr[i - 1]

 

① 장점

• 입력으로 들어오는 배열의 원소가 정렬되어 있으면 속도가 빠릅니다. ( 모두 정렬이 되어있으면 O(n) )
• 이미 정렬되어 있는 배열에 원소를 삽입/제거하는 경우에 효율적인 알고리즘입니다.
• Stable 정렬과 In-place 정렬에 해당합니다.

② 단점

• 평균과 최악의 시간복잡도가 O(n²)에 해당합니다.
• 배열의 길이가 길어질수록 비효율적입니다.

---

2-5. Quick Sort ( 퀵 정렬 )

출처 : https://east-star.tistory.com/10

  - 분할 정복( Divide and Conquer ) 방법을 통한 정렬로, 하나의 축(pivot)을 정해서 축보다 작은 값은 왼쪽에 큰 값은 오른쪽에 정렬하는 방법입니다.

분할 정복

분할( Divide ) - 문제를 분할하여 비슷한 유형의 작은 문제로 분할이 가능할 때까지 나눈다.

정복( Conquer ) - 각 문제를 재귀적(반복적)으로 해결한다.

  - 분할( Divide ) : pivot(축)을 선택하여 배열을 나눈다. (왼쪽과 오른쪽)

  - 정복( Conquer ) : pivot을 기준으로 pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬한다.

  - 일반적으로는 준수한 효율을 보이기 때문에 대부분의 내장 라이브러리에서 존재하는 정렬 함수는 QuickSort를 사용하고 있습니다.

def QuickSort(arr):
  if len(arr) <= 1: 
    return arr
  
  pivot = arr[0]
  tail = arr[1:]
  
  left = [x for x in tail if x <= pivot] # pivot보다 작거나 같으면 왼쪽
  right = [x for x in tail if x > pivot] # pivot보다 크면 오른쪽
  
  return QuickSort(left) + [pivot] + QuickSort(right)

 

① 장점

• 불필요한 데이터의 이동을 줄일 수 있습니다.
• 최선과 평균의 경우 O(n log n)의 시간 복잡도를 가지고 있어 다른 정렬 알고리즘에 비해 빠른 편입니다.
• In-place 정렬입니다.

② 단점

• 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸릴 수 있습니다.
• pivot이 최솟값이나 최댓값으로 선택되어 분할이 불균형하게 이루어지는 경우 O(n²)의 시간복잡도를 가질 수 있습니다.
• Unstable 정렬입니다.

---

2-6. Merge Sort ( 병합 정렬 )

출처 : https://east-star.tistory.com/10

  - 퀵 정렬과 마찬가지로 분할 정복( Divide and Conquer ) 방법을 이용한 정렬입니다.

  - 분할( Divide ) : 배열을 더 이상 쪼갤 수 없는 단위( 1~2개 부분 배열 )까지 분할합니다.

  - 정복( Conquer ) : 나누어진 부분 배열을 정렬합니다.

  - 분할·정복을 통해 정렬된 배열을 마지막에 병합(Merge)하여 정렬을 완료합니다.

# Conquer
def Merge(left, right):
  result = []
  i, j = 0, 0
  
  while i < len(left) and j < len(right):
    if left[i] < right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  
  while i < len(left):
    result.append(left[i])
    i += 1
  
  while j < len(right):
    result.append(right[j])
    j += 1
  
  return result

# Divide
def MergeSort(arr):
  if len(arr) <= 1:
    return arr
  
  mid = len(arr) // 2
  left = arr[:mid]
  right = arr[mid:]
  
  left = MergeSort(left)
  right = MergeSort(right)
  
  return Merge(left, right)

① 장점

• 시간 복잡도가 최선, 평균, 최악이 모두 O(n log n)에 해당하며 빠른 정렬에 속합니다.
• Stable 정렬입니다.

② 단점

• 정렬을 하는 배열 이외에 추가적인 메모리 ( 임시 배열 )이 필요로 합니다.
• Not In-place 정렬입니다.

---

2-7. Heap Sort ( 힙 정렬 )

  - 힙(Heap) : 우선순위 큐( Queue에 우선순위의 개념을 접목 )를 위해 고안된 완전이진트리 형태의 자료구조

  - 완전이진트리(Complete Binary Tree) : 이진트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리

  - 최대 힙 트리 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리

  - 최소 힙 트리 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

  - 힙 정렬 개념

• 정렬해야 할 n개의 요소들로 힙(Heap)을 만듭니다. ( 내림차순은 최대 힙, 오름차순은 최소 힙)
• 힙 트리로 구한 최댓값(최솟값)에 해당하는 root 노드를 빼내면서 정렬을 수행합니다.

def heapify(arr,n,i):
  root = i
  left = 2*i + 1
  right = 2*i + 2
  
  # 왼쪽 노드가 존재하고, 루트보다 더 큰 값일 때
  if left < n and arr[root] < arr[left]:
    root = left
  
  # 오른쪽 노드가 존재하고, 루트보다 더 큰 값일 때
  if right < n and arr[root] < arr[right]:
    root = right
      
  # 왼쪽, 오른쪽 자식 노드들과 바꿔줄 위치를 찾았을 때
  if root != i:
    # 찾아낸 값과 swap
    arr[i],arr[root] = arr[root],arr[i]
    # 계속 heap 형태를 갖출 때까지 실행
    heapify(arr,n,root)


def HeapSort(arr):
  n = len(arr)
    
  # heap 형태로 데이터를 정렬한다.
  for i in range(n,-1,-1):
    heapify(arr,n,i)
  
  # root와 마지막값을 바꿔 정렬하고 바뀐값을 기준으로 다시 heapify
  for i in range(n-1,0,-1):
    arr[i],arr[0] = arr[0],arr[i]
    heapify(arr,i,0)
      
  return arr

 

① 장점

• 최댓값, 최솟값을 구할 때 매우 유용합니다.
• 항상 같은 시간 복잡도 O(n log n)를 유지하기 때문에 성능이 준수합니다.
• 주어진 배열 내부에서 위치를 바꾸는 방식을 적용하면 In-place 정렬도 가능합니다.

② 단점

• 퀵 정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않습니다.
• Unstable 정렬입니다.

③ Python "heapq" 라이브러리

  - python에서는 heapq 모듈을 통해 힙을 제공합니다.

import heapq

arr = []

heapq.heapify(arr) # 기존의 리스트를 Heap 형태로 변환

# 힙 형태를 유지하면서 n값 추가
heapq.heappush(arr, 3) # arr = [3]
heapq.heappush(arr, 1) # arr = [1, 3]
heapq.heappush(arr, 2) # arr = [1, 3, 2]

# 힙 형태를 유지하면서 가장 작은 원소를 꺼낸다.
heapq.heappop(arr) # arr = [2, 3]

 

  heapq를 이용한 heap정렬

import heapq

def HeapSort_heapq(arr):
  heapq.heapify(arr)

  result = [] 
  for i in range(len(arr)):
    x = heapq.heappop(arr)
    result.append(x)
    
  return result

arr = [0, 1, 5, 7, 4, 3, 2, 6]
HeapSort_heapq(arr) # [0, 1, 2, 3, 4, 5, 6, 7]

---

3. 그 외 정렬

위의 정렬들은 가장 많이 알려진 정렬이고, 다음의 정렬들은 이번에 공부하면서 새롭게 알게 된 정렬입니다.

 

3-1. Counting Sort ( 계수 정렬 )

  - 데이터의 크기를 비교하지 않고, 각 데이터의 개수를 파악하여(Counting) 이를 앞 순서대로 정렬하는 방식입니다.

 

    1) 인덱스를 이용한 계수정렬 ( Unstable )

        - 가장 큰 데이터의 값을 담을 수 있는 카운팅 배열(Counting)과 결과 값을 담을 배열(result)을 준비합니다.

        - 인덱스를 활용해 카운팅 배열에 데이터 값의 개수를 더합니다.

        - Counting에서 0이 아닌 값들의 위치를 찾아 result에 해당 값만큼 인덱스를 넣어줍니다. 

def CountingSort(arr):
  Counting = [0] * (max(arr)+1)
  result = []

  for num in arr:
    Counting[num] += 1

  for idx in range(len(Counting)):
    if Counting[idx] != 0:
      for _ in range(Counting[idx]):
        result.append(idx)
  
  return result

arr = [1, 3, 5, 4, 2, 1, 2]
CountingSort(arr) # [1, 1, 2, 2, 3, 4, 5]

 

    2) 누적합을 이용한 계수정렬 ( Stable )

        - 가장 큰 데이터의 값을 담을 수 있는 카운팅 배열(Counting)과 결과 값을 담을 배열(result)을 준비합니다.

        - 누적합을 활용해 카운팅 배열에 데이터 값의 개수를 더합니다.

        - Counting에서 arr의 데이터 인덱스를 찾아 result에 바로 대입합니다.

# 누적합을 이용한 정렬
def CountingSort(arr):
  Counting = [0] * (max(arr)+1)
  result = [0] * len(arr)

  for i in arr:
    Counting[i] += 1

  # 누적합을 이용하여 Counting 갱신
  for i in range(1, len(Counting)):
    Counting[i] += Counting[i-1]

  # Stable한 정렬을 하기위해 뒤에서 부터 찾기
  for num in ragne(len(arr)-1, -1, -1):
    i = arr[num]
    
    idx = Counting[i]
    result[idx-1] = i # idx의 첫번째는 0이기 때문에 -1
    Counting[i] -= 1
  
  return result

 

① 장점

• 중복된 값이 많은 정렬을 정렬할 때 유리합니다.
• O(n)의 시간복잡도를 가집니다.

② 단점

• 정확한 시간 복잡도는 O(n + k)이며 k는 정렬하고자 하는 배열에서의 가장 큰 값입니다.
• 따라서, 입력 데이터의 최댓값에 따라 카운팅 배열의 크기가 매우 커질 수 있습니다. ( 메모리 낭비 발생 )
• 인덱스를 이용하는 정렬이기 때문에 데이터가 양의 정수인 경우에 사용할 수 있습니다.
• Not In-place 정렬입니다.

---

3-2. Radix Sort ( 기수 정렬 )

  - 데이터의 각 자릿수를 낮은 자릿수에서부터 가장 큰 자릿수까지 올라가면서 정렬합니다.

  - 최대 자릿수를 구하고, bucket배열을 만들어 순서대로 (1의 자리, 10의 자리, 100자리...) 같은 원소들을 생성한 배열에 모읍니다.

  - 비교연산을 하지 않아 빠른 정렬 속도를 보여줍니다.

  - 나올 수 있는 값의 최대 사이즈가 9이기 때문에, 계수 정렬의 단점을 보완할 수 있습니다.

from collections import deque

def RadixSort(arr):
  buckets = [deque() for _ in range(10)]

  queue = deque(arr) 
  maxNum = max(arr) # 가장 큰 값
  digit = 1 # 자리수

  while maxNum >= digit:
    while queue:
      number = queue.popleft()
      
      idx = (number // digit) % 10 
      buckets[idx].append(number) # 자리수에 맞게 넣기
    
    # queue 재 정렬
    for bucket in buckets:
      while bucket:
        queue.append(bucket.popleft())
    
    digit *= 10 # 자리수 점차 늘리기
    
  return list(queue)

① 장점

• O(dn) 시간복잡도로 빠른 정렬을 보여줍니다. ( d는 데이터들의 최대 자릿수를 의미합니다. )
• Stable 정렬입니다.

② 단점

• 자릿수가 없는 것은 정렬할 수 없습니다. ( 부동 소수점 )
• 중간 과정을 담을 수 있는 bucket 공간이 필요합니다.
• Not In-plcae 정렬입니다.

---

3-3. Shell Sort ( 셸 정렬 )

  - Donald L. Shell이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에서 빠르게 정렬된다는 사실에 착안한 방법입니다.

  - 방법

     1) 정렬할 배열을 일정한 간격(Gap)으로 나눕니다. ( 일반적으로는 반으로 나눈 값으로 시작합니다. )

     2) 일정한 Gap으로 나눈 배열에 대해 삽입 정렬을 수행합니다.

     3) 점차 Gap을 줄여가며 정렬을 반복합니다.

def InsertionSort(arr, first, last, gap):
  idx = first + gap
  
  while idx <= last:
    cur = arr[idx]
    position = idx
    
    while (position > first) and (arr[position - gap] > cur):
      arr[position] = arr[position - gap]
      position -= gap
    
    arr[position] = cur
    idx += gap

def ShellSort(arr):
  n = len(arr)
  gap = n // 2
  
  while gap > 0:
    for start in range(gap):
      InsertionSort(arr, start, n-1, gap)
    gap //= 2

  return arr

 

① 장점

• 어느 정도 정렬된 배열에서 O(n) 시간복잡도로 빠른 속도를 보여줍니다.
• Stable 정렬입니다.

② 단점

• 일정한 간격에 따라 배열을 보기 때문에, 간격 설정을 잘못할 경우 성능이 저하될 수 있습니다.

---

4. 시간 복잡도 정리

정렬	최악 ( Worst )	평균 ( Average )	최선 ( Best )
Bubble Sort ( 버블정렬 )	O(n²)	O(n²)	O(n²)
Selection Sort ( 선택정렬 )	O(n²)	O(n²)	O(n²)
Insertion Sort ( 삽입정렬 )	O(n²)	O(n²)	O(n)
Quick Sort ( 퀵 정렬 )	O(n²)	O(nlogn)	O(nlogn)
Merge Sort ( 병합 정렬 )	O(nlogn)	O(nlogn)	O(nlogn)
Heap Sort ( 힙 정렬 )	O(nlogn)	O(nlogn)	O(nlogn)
Counting Sort ( 계수 정렬 )	O(n)	O(n)	O(n)
Radix Sort ( 기수 정렬 )	O(n)	O(n)	O(n)
Shell Sort ( 셸 정렬 )	O(n²)	O(n^1.5)	O(n)

---

 

Big O Notation: A Complete Overview With Real-World Applications

https://east-star.tistory.com/10

 

정렬 알고리즘(Sorting Algorithm) 정복하기 - with JS

https://velog.io/@swhan9404/%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC-%EC%B9%B5%ED%85%8C%EC%9D%BC%EC%A0%95%EB%A0%AC-%EB%B9%97%EC%A7%88%EC%A0%95%EB%A0%AC

버블정렬, 칵테일정렬, 빗질정렬

https://mong9data.tistory.com/45

[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)