[Algorithm]정렬 알고리즘 -2 (Sorting Algorithm)

✏️ 정렬알고리즘의 종류

• $O(n^2)$ 정렬 알고리즘
  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬
• $O(nlogn)$ 정렬 알고리즘
  • 퀵 정렬
  • 병합 정렬
  • 트리 정렬
  • 힙 정렬
• 특수 알고리즘
  • 계수 정렬
  • 기수 정렬

퀵 정렬(Quick Sort)

 퀵 정렬은 이름에서와 같이 극단적인 경우를 제외하고 $O(nlogn)$ 정렬 알고리즘 중에서 가장 빠른 정렬이다. pivot이라고 불리는 '적절한' 원소 하나를 기준 삼아 기준보다 작으면 앞으로, 크면 뒤로 빼는 등의 방법을 사용한다.

 퀵 정렬은 분할-정복을 기반으로 하며, 재귀로 구현할 수 있다. 퀵 정렬에서 pivot을 기준으로 나누는 것이 매우 중요한데 이것을 partition step이라고 하며 성능에 많은 영향을 준다. 여러 기준이 있지만 평균적으로 배열의 중앙을 기준으로 삼는다.

python 구현 방법

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

def quickSort(data, low, high):
    p = data[(low + high) // 2] # 배열의 중앙값을 기준으로 잡음
    left, right = low, high
    while True:
        while data[left] < p: left += 1
        while data[right] > p: right -= 1
        if left >= right: break
        data[left], data[right] = data[right], data[left]
    if low < right: quickSort(data, low, right)
    if left < high: quickSort(data, right + 1, high)
    return data

quickSort(sample, 0, len(sample) - 1) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

병합 정렬(Merge Sort)

 병합 정렬은 원소의 갯수가 0 또는 1이 될 때까지 절반으로 계속 쪼갠 뒤 모두 분해되면 하나씩 합쳐 가면서 정렬을 수행한다. 병합된 부분은 이미 정렬이 완료된 상태이기 때문에 전체를 비교하지 않아도 된다는 장점이 있다.

 시간복잡도가 $O(nlogn)$이지만 퀵 정렬보다는 성능이 조금 떨어진다. 하지만 안정 정렬(stable sort)이기 때문에 데이터의 상태에 영향을 받지 않는다는 장점이 있다. 병합 정렬은 분할-정복 구조의 형태로 표현될 수 있으며 재귀를 사용해 구현할 수 있다.

python 구현 방법

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

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0: # 왼쪽과 오른쪽 배열이 모두 존재한다면
        if left[0] <= right[0]:             # 왼쪽이 더 작으면 왼쪽을 추가
            result.append(left[0])
            left = left[1:]
        else:                               # 아니라면 오른쪽을 추가
            result.append(right[0])
            right = right[1:]
    # 두 배열 중 하나는 먼저 끝나므로 남은 값은 뒤에 붙여 넣고 반환(없어도 상관 없음)
    result.extend([*left, *right])
    return result

def mergeSort(data):
    if len(data) <= 1:
        return data
    mid = len(data) // 2
    left = mergeSort(data[:mid])
    right = mergeSort(data[mid:])
    return merge(left, right)

mergeSort(sample)

❓안정 정렬(stable sort)과 불안정 정렬(unstable sort)

 안정 정렬이란 중복된 값을 입력 순서와 동일하게 정렬하는 것을 말한다. 동일한 값이 있을 때 정렬한 이후 결과값에서 중복된 값들의 순서가 변하면 불안정 정렬이고 변하지 않으면 안정 정렬이다.

 안정 정렬에는 삽입, 병합, 버블, 계수 정렬 등이 있으며 불안정 정렬에는 선택, 힙, 셸, 퀵 정렬 등이 있다.

트리 정렬(Tree Sort)

 트리 정렬이란 이진 트리를 기반으로 하는 정렬 방법이다. 트리를 생성할 때 자신보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 가도록 규칙을 만드는 방법이다.

 이진 트리를 만드는 가장 간단한 방법은 자기 자신의 값과 왼쪽과 오른쪽에 어떤 값이 있는지에 대한 정보를 가진 객체를 생성하여 할당하는 것이다.

python 구현 방법

# 노드 정의하기
class Node:
    def __init__(self, item = 0):
        self.key = item
        # 왼쪽 값과 오른쪽 값 정의
        self.left = None
        self.right = None

root = Node()

def insert(root, key): # insert method 구현
    if root is None:
        return Node(key)
  
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
   
    return root

def treeinsert(data, root):
    for key in data:
        root = insert(root, key)

def inorderRec(root, answer):
    if (root != None):
        inorderRec(root.left, answer)
        answer.append(root.key)
        inorderRec(root.right, answer)

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

treeinsert(sample, root)
inorderRec(root, answer)
print(answer[1:]) # 탐색 시작 시점에서 들어간 루트 노드 제외

힙 정렬(Heap Sort)

 힙 정렬은 완전 이진 트리를 기반으로 하는 정렬 방법이다. 힙은 여러 값 중 최대값이나 최솟값을 빠르게 찾기 위해 사용하는 자료 구조이며 이 성질을 이용해서 정렬하는 것이다.

 추가적인 메모리가 전혀 필요 없다는 점과 항상 $O(nlogn)$의 성능을 보장할 수 있다는 장점이 있다. 파이썬에서는 heapq라는 내부 라이브러리를 사용하여 구현할 수 있다.

python 구현 방법

# 내부 라이브러리를 사용하지 않는 방법
sample = [3, 0, 1, 8, 7, 2, 5, 4, 6, 9]

def heapify(data, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and data[i] < data[left]:
        largest = left

    if right < n and data[largest] < data[right]:
        largest = right
  
    if largest != i:
        data[i], data[largest] = data[largest], data[i]
        heapify(data, n, largest)

def heapSort(data):
    n = len(data)
    for i in range(n, -1, -1):
        heapify(data, n, i)
   
    for i in range(n - 1, 0, -1):
        data[i], data[0] = data[0], data[i]
        heapify(data, i, 0)

heapSort(sample)
print(sample)

# 내부 라이브러리를 사용하는 방법
from heapq import heappush, heappop

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

def heapSort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

print(heapSort(sample))