빽 투더 기본기 [알고&자구 1편]. 정렬

기본 정렬에 대해서 정리해 놓는다.
그냥 나 알아보기 쉽게, 직관적으로만 설명한다.

시간 복잡도 O(n^2) 정렬

선택 정렬

뒤에 가장 큰, 또는 가장 작은 값을 현재 인덱스 뒤부터 찾아, 앞의 인덱스부터 하나씩 채워나가는 정렬.

# selection sort
a = [3,1,2,5,4,6,7]
size = len(a)
for i in range(size):
    for j in range(i+1, size):
        if a[j] < a[i]:
            a[i], a[j] = a[j], a[i]
print(a)

버블 정렬

뒤에 가장 큰, 또는 가장 작은 값을 뒤로 밀어밀어 보내, 마지막 인덱스부터 하나씩 채워나가는 정렬

# bubble sort
a = [3,1,2,5,4,6,7]
size = len(a)
for i in range(size):
    for j in range(i+1, size):
        if a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
print(a)

삽입 정렬

차근차근 정렬을 쌓아오며, 필요한 경우 모두 일괄적으로 땡기며 정렬

# insertion sort
a = [3,1,2,5,4,6,7]
size = len(a)
for i in range(1, size):
    tmp, j = a[i], i-1
    while j >= 0 and a[j] > tmp:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = tmp
print(a)

• 정렬이 다 된건 아니지만, 그래도 좀 정렬이 되어있으면, 다른 정렬들보다 효율적
• 구현 상, Best 시간 복잡도가 O(n) 이다. (모두 정렬되어있는 경우)

시간 복잡도 O(n log n) 정렬

머지 정렬

분할 정복으로, 데이터를 반으로 계속 쪼개나가다가 다시 하나씩 정렬하며 정복하는 정렬

# merge sort
def merge_sort(a):
    size = len(a)
    if size >= 2:
        # 반으로 쪼갠다. 왼쪽, 오른쪽 파트로.
        l, r = merge_sort(a[:size//2]), merge_sort(a[size//2:])      
        ret = []
        i, j = 0, 0

        # 쪼개어진 왼쪽 파트, 오른쪽 파트를 비교하며, 정렬된 새로운 리스트를 만든다.
        while i < len(l) and j < len(r):
            if l[i] <= r[j]:
                ret.append(l[i])
                i += 1
            else:
                ret.append(r[j])
                j += 1
        # 왼쪽, 오른쪽 파트에 남겨진 아이템들을 마저 새로운 리스트에 넣어준다.
        while i < len(l):
            ret.append(l[i])
            i += 1
        while j < len(r):
            ret.append(r[j])
            j += 1       
        # 정렬된 새로운 리스트 반환
        return ret
    else:
        return a
a = [3,1,2,5,4,6,7]
print(merge_sort(a))

퀵 정렬

머지 정렬은 가운데를 딱 나누는 반면, 퀵 정렬은 그냥 임의의 한 값 (pivot)을 기준으로 반반 나눈다.

# quick sort
def quick_sort(a):
    size = len(a)
    if size >= 2:
        # 임의의 값, 여기서는 0번째 값을 pivot으로 둔다.
        pivot = a[0]
        # pivot 을 기준으로 반반 나눈다.
        lesser = [e for e in a[1:] if e <= pivot]
        greater = [e for e in a[1:] if e > pivot]
        # 반반 한거 정렬한 뒤 합친 리스트 반환
        return quick_sort(lesser) + [pivot] + quick_sort(greater)
    else:
        return a
a = [3,1,2,5,4,6,7]

• 최악의 경우 O(n^2) 까지 뜨지만, 평균적으로 가장 빠르다고 한다. 그래서 퀵.
• pivot 값을 무엇을 잡느냐에 따라 시간 최적화가 가능하다.

힙 정렬

힙이라는 자료구조를 이용해 정렬하는 정렬.
우선순위를 고려하는 자료구조인 힙을 먼저 알아야한다. 그리고 힙을;;; 짜야한다.

# heap sort
class min_heap:
    def __init__(self, arr):
        self.a = []
        self.heap_size = 0
        for e in arr:
            self.insert(e)

    def insert(self, e):
        self.a.append(e)
        self.heap_size += 1
        self.heapify(0)

    def delete(self):
        ret = self.a[0]
        self.a[0] = self.a[-1]
        self.a.pop()
        self.heap_size -= 1
        self.heapify(0)
        return ret

    def heapify(self, index):
        left_index, right_index = 2 * index + 1, 2 * index + 2
        smallest = index
        if left_index < self.heap_size and self.a[left_index] < self.a[smallest]:
            smallest = left_index
        if right_index < self.heap_size and self.a[right_index] < self.a[smallest]:
            smallest = right_index
        if smallest != index:
            self.a[index], self.a[smallest] = self.a[smallest], self.a[index]
            self.heapify(smallest)

    def sort(self):
        from copy import deepcopy
        tmp = deepcopy(self.a)
        ret = []
        while self.a:
            ret.append(self.delete())
        self.a = tmp
        return ret

a = [3,1,2,5,4,6,7]
print(min_heap(a).sort())

참고한 링크

Heejeong Kwon님 블로그. 삽입 정렬이란

Ratsgo's blog. 퀵 정렬

열코의 프로그래밍 일기. 정렬 알고리즘 종류