[알고리즘] 정렬 - 버블정렬, 선택정렬, 삽입정렬, 퀵소트(퀵정렬) , 배열정렬, 병합정렬, 힙정렬

---

버블 정렬(Bubblesort)

계속 한자리 옆의 자료와 비교하면서, 순서가 맞으면 두고, 다르면 교환하는 방식

가장 쉽고 직관적인 버블 정렬!

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …
이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식입니다!
작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하시면 됩니다! 

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6을 비교합니다!
        4 < 6 이면 그대로 둡니다.

2단계 : [4, 6, 2, 9, 1]
           6과 2를 비교합니다!
           6 > 2 이므로 둘을 변경합니다!
       [4, 2, 6, 9, 1] 이렇게요!

3단계 : [4, 2, 6, 9, 1]
              6과 9를 비교합니다!
              6 < 9 이면 그대로 둡니다.

4단계 : [4, 2, 6, 9, 1]
                 9와 1를 비교합니다!
                 9 > 1 이므로 둘을 변경합니다!
       [4, 2, 6, 1, 9] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!

5단계 : [4, 2, 6, 1, 9]
        4와 2을 비교합니다!
        4 > 2 이므로 둘을 변경합니다.
       [2, 4, 6, 1, 9] 이렇게요!

6단계 : [2, 4, 6, 1, 9]
           4와 6을 비교합니다!
           4 < 6 이면 그대로 둡니다.

7단계 : [2, 4, 6, 1, 9]
              6와 1을 비교합니다!
              6 > 1 이므로 둘을 변경합니다!
       [2, 4, 1, 6, 9] 이렇게요!

그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!

8단계 : [2, 4, 1, 6, 9]
        2와 4을 비교합니다!
        2 < 4 이면 그대로 둡니다.

9단계 : [2, 4, 1, 6, 9]
           4와 1을 비교합니다!
           4 > 1 이므로 둘을 변경합니다!
       [2, 1, 4, 6, 9] 이렇게요!

자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!

10단계 : [2, 1, 4, 6, 9]
         2와 1을 비교합니다!
         2 > 1 이므로 둘을 변경합니다!
        [1, 2, 4, 6, 9] 이렇게요!

자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?

 

 

test_sort.py

from sort.sorts import bubblesort

assert bubblesort([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert bubblesort([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

 

sorts.py

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    # 제일 첫번째 값은 어차피 가장 작은 값이 될 것이므로, 그보다 큰 값만 찾아내면됨
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        # 전체 반복값에서 이미 순서를 구한 개수는 뺀다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

 

---

 

선택 정렬(Selectionsort)

이름에서 알 수 있듯이 선택 해서 정렬한다! 라고 생각하시면 됩니다.

다음과 같이 사람들이 일렬로 쭉~ 서 있는데,
한번 쓱 둘러보면서 가장 키 작은 사람을 찾는겁니다.
그리고 전부 다 봤다면, 그 중 가장 키 작은 사람! 맨 앞으로 와! 한 다음에
또 둘러보면서 두 번째로 키 작은 사람을 두 번째에 배치 시킵니다. 

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6과 2와 9와 1을 차례차례 비교합니다.
	      그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
       [1, 6, 2, 9, 4] 이렇게요!

자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.

2단계 : [1, 6, 2, 9, 4]
           6과 2와 9와 4를 차례차례 비교합니다.
           그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
       [1, 2, 6, 9, 4] 이렇게요!

3단계 : [1, 2, 6, 9, 4]
              6과 9와 4를 차례차례 비교합니다.
              그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
       [1, 2, 4, 9, 6] 이렇게요!

4단계 : [1, 2, 4, 9, 6]
                 9와 6을 비교합니다!
                 그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
       [1, 2, 4, 6, 9] 이렇게요!


자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!

 

assert selectionsort([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert selectionsort([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

 

test_sort.py

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
    	# 최초값은 0
        minimun = iter
        # 1번째 값부터 0번째 값과 비교, 더 작다면 그 위치를 minimun으로 지정
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur
		
        # 최소값이 갱신되었다면 자리를 서로 바꿔준다.
        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

 

---

 

삽입 정렬(Insertionsort)

선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,

삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다!

 

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,

삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!

 

이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데,

다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서 아 여기가 내 자리구나! 하면서 삽입하며 정렬하는 방식입니다.

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4는 현재 정렬되어 있는 부대원입니다. 
			  그럼 이제 새로운 신병인 6을 받습니다.
        4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
       [4, 6, 2, 9, 1] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!

2단계 : [4, 6, 2, 9, 1]
        4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 2를 받습니다.
        4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
        4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
       [2, 4, 6, 9, 1] 이렇게요!

3단계 : [2, 4, 6, 9, 1]
        2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 9를 받습니다.
        2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
       [2, 4, 6, 9, 1] 이렇게요!

4단계 : [2, 4, 6, 9, 1]
        2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 1을 받습니다.
        2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
        2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
        2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
        2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
       [1, 2, 4, 6, 9] 이렇게요!

자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?

assert insertionsort([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert insertionsort([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

assert insertionsort_2([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert insertionsort_2([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있다고 가정하고, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst


def insertionsort_2(lst):
    for idx in range(1, len(lst)):
        val = lst[idx]
        cmp = idx - 1

        while lst[cmp] > val and cmp >= 0:
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        lst[cmp + 1] = val

    return lst

 

---

지금까지 봤던 정렬들은 모두 시간복잡도가 O(n**2)으로, 상당히 느린 편이다.

이제부터 알아본 퀵소트는, 이미 잘 정렬되어있는 배열은 worst case로 O(n**2)가 나오지만,

best case는 N*O(logN) 으로, 훨씬 빨라진다!

---

퀵소트(Quicksort)

분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘입니다.

배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide).

그리고 그 사이에 기준을 위치시킵니다.

작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다.

[1, 6, 2, 9, 4]  # 정렬되지 않은 배열
# i : 피벗의 값보다 작은 값들이 모여있는 범위 ➡️ 처음엔 몇개인지 알 수 없으므로 -1로 설정
# j : 내가 지금 보고있는 인덱스(몇번째 값까지 봤는지 표시하는 역할)

1단계: [1, 6, 2, 9, 4]
	  # 보통 퀵소트 마지막 원소를 피벗으로 삼음
      마지막 원소인 4를 pivot으로 삼습니다.
	  pivot보다 작은 집합의 인덱스 i를 -1로 설정합니다.
	  (i=-1)

2단계: [1, 6, 2, 9, 4]
      # j는 값을 비교하기 위해 하나씩 올라감
	  j를 0에서부터 3까지 살펴봅니다. 
	  j가 0이므로 지금 살펴보고 있는 값은 1 입니다.
      1는 pivot(4)보다 작습니다.
			i를 1 증가시켜 0으로 만듭니다. # 작은 값들의 범위인 i를 한칸 넓히는 것
			i 와 j 의 위치를 바꿉니다.
      i와 j가 동일하므로 아무 일도 일어나지 않습니다.
			(i=0, j=0)

3단계: [1, 6, 2, 9, 4]
	  j를 1 증가시켜 1로 만듭니다.
	  지금 살펴보고 있는 값은 6 입니다.
      6은 pivot(4)보다 큽니다.
	  넘어갑니다.
			(i=0, j=1)

4단계: [1, 6, 2, 9, 4]
	  j를 1 증가시켜 2로 만듭니다.
	  지금 살펴보고 있는 값은 2 입니다.
      2는 pivot(4)보다 작습니다.
			i를 1 증가시켜 1로 만듭니다.
			i(1) 와 j(2) 의 위치를 바꿉니다.
			배열은 [1, 2, 6, 9, 4]가 됩니다.
			(i=0, j=2)

5단계: [1, 2, 6, 9, 4]
	  j를 1 증가시켜 3으로 만듭니다.
	  지금 살펴보고 있는 값은 9 입니다.
      9는 pivot(4)보다 큽니다.
			넘어갑니다.
			(i=1, j=3)

6단계: j를 0부터 3까지 모두 살펴보았습니다.
	  i는 pivot보다 작은 집합의 범위를 나타내므로, 
      i+1과 pivot의 위치를 바꿉니다.
	  배열은 [1, 2, 4, 9, 6] 이 됩니다.

7단계: [1, 2]와 [9, 6]을 대상으로 1~6단계를 반복합니다.
      결과적으로 [1, 2, 4, 6, 9]가 됩니다.
			정렬이 끝났습니다.

 

시간복잡도

worst case, 1 2 3 4 5 6 7 8 9 10

순차정렬의 경우, 원소가 하나씩만 빠지고 계속 하나씩 연산을 해야함

=> 최악의 경우 등차수열의 합으로 O(n**2) 의 시간복잡도 가짐

 

best case, 1 4 2 3 6 7 10 9 8 5

집합이 절반으로 나뉘게 되면 각 연산마다 n 번씩만 돈다. 

=> 일반적으로 시간복잡도는 N*O(logN)

 

퀵소트 구현 

알고리즘 테스트에 많이 나오므로 아는 것 매우 중요하다!

# quicksort(리스트,시작점,끝점)
assert quicksort([4, 6, 2, 9, 1], 0, 1) == [4, 6, 2, 9, 1] # 0부터 1까지만 정렬
assert quicksort([4, 6, 2, 9, 1], 0, 2) == [2, 4, 6, 9, 1]
assert quicksort([4, 6, 2, 9, 1], 0, 3) == [2, 4, 6, 9, 1]
assert quicksort([4, 6, 2, 9, 1], 0, 4) == [1, 2, 4, 6, 9]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 1) == [2, 3, 1, 5, 3, 2, 3]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 2) == [1, 2, 3, 5, 3, 2, 3]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 3) == [1, 2, 3, 5, 3, 2, 3]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 4) == [1, 2, 3, 3, 5, 2, 3]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 5) == [1, 2, 2, 3, 3, 5, 3]
assert quicksort([3, 2, 1, 5, 3, 2, 3], 0, 6) == [1, 2, 2, 3, 3, 3, 5]

def quicksort(lst, start, end):
    def partition(part, ps, pe):
    	# 제일 마지막 요소를 피벗으로 삼음
        pivot = part[pe]
        # i (피벗보다 작은 것들의 집합) : 시작점 - 1
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]
                
        # i+1위치의 값과 피벗(가장 끝값)의 위치를 바꾼다.
        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    # 리스트의 길이가 1이거나 start가 end보다 크면 재귀함수 실행하지 않음
    if len(lst) == 1:
        return lst
    
    if start >= end:
        return None

    p = partition(lst, start, end)
    # 왼쪽기준/ 오른쪽기준으로 다시 재귀적으로 정렬
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst

 

---

배열 정렬

https://leetcode.com/problems/sort-an-array/description/

시간 초과! 최악의 경우에 당첨되었습니다. (25억 번 연산 필요)

하지만 아래 한 줄이면 문제는 손쉽게 통과할 수 있습니다. 어떻게 이게 가능할까요?

앞으로 최악의 경우에도 O(nlogn)을 보장하는 mergesort, heapsort 알고리즘을 알아보겠습니다.

return sorted(nums)

---

 

Mergesort(병합 정렬)

정렬되지 않았던 배열이 정렬이 되었다!

 

이제부터는 면접에서 직접 구현해보라고 하는 구현 방법들입니다.

우선, 두 집합을 어떻게 합쳐서 정렬할 수 있는지 예시로 보면서 이해해보겠습니다.

[1, 2, 3, 5]  # 이미 정렬된 배열 A
[4, 6, 7, 8]  # 이미 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C


        ↓
1단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        1과 4를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]

           ↓ # 하나 넣었으니 이 배열은 화살표 한 칸 옮김
2단계 : [1, 2, 3, 5] 
        ↓ # 여기는 아직 넣지 않았으므로 그대로
       [4, 6, 7, 8] 
        2와 4를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]


              ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        3과 4를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]

                 ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        5와 4를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]

                 ↓
3단계 : [1, 2, 3, 5] 
           ↓
       [4, 6, 7, 8] 
        5와 6을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5]

엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다. (merge)
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

그러면 A 와 B를 합치면서 정렬할 수 있었습니다.

 

merge 구현

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    # 비교 끝난 후 만약 i가 아직 끝까지 안갔다면, 나머지 끝까지 붙여준다.
    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    # 비교 끝난 후 만약 j가 아직 끝까지 안갔다면, 나머지 끝까지 붙여준다.
    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result

 

mergesort

assert mergesort([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert mergesort([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

def mergesort(lst):
    # 요소가 하나만 남았을 때는 그냥 그 하나만 반환
    if len(lst) <= 1:
        return lst
    
    # 반으로 쪼갠다.
    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    
    # 왼쪽/ 오른쪽 각각 병합정렬 후 두 배열을 합친다.
    return merge(mergesort(L), mergesort(R))

항상 집합이 2개씩 쪼개짐, 각각 n번씩 연산이됨

 

위의 케이스에서 봤듯이,

저희는 [1, 2, 3, 4, 5, 6, 7, 8] 을 정렬하기 위해 [1, 2, 3, 5] 과 [4, 6, 7, 8] 을 병합했습니다.

 

[1, 2, 3, 5] 과 [4, 6, 7, 8] 을 정렬하기 위해 [3, 5] [1, 2] 과 [6, 8] [4,7] 을 병합했습니다.

 

[3, 5] [1, 2] 과 [6, 8] [4,7] 을 정렬하기 위해 [5] [3] [2] [1] [6] [8] [7] [4] 를 병합했습니다.

 

이를 얼마나 시간이 걸리는지에 대한 관점으로 보면, T(N) 을 N 의 길이를 정렬하기 위해 걸리는 시간이라고 하겠습니다.

 

1단계

[1, 2, 3, 4, 5, 6, 7, 8] 을 정렬하기 위해 [1, 2, 3, 5] 과 [4, 6, 7, 8] 을 병합했습니다.

즉, 크기 N 인 배열을 정렬하기 위해 크기 N/2 인 부분 배열 2개를 비교 합니다.

그러면 N/2 * 2 = N 번 비교하게 됩니다!

 

2단계

[1, 2, 3, 5] 과 [4, 6, 7, 8] 을 정렬하기 위해 [3, 5] [1, 2] 과 [6, 8] [4,7] 을 병합했습니다.

즉, 크기 N/2 인 부분 배열 2개를 정렬하기 위해 크기 N/4 인 부분 배열 4개를 비교 합니다.

그러면 N/4 * 4 = N 번 비교하게 됩니다!

 

3단계

[3, 5] [1, 2] 과 [6, 8] [4,7] 을 정렬하기 위해 [5] [3] [2] [1] [6] [8] [7] [4] 를 병합했습니다.

즉, 크기 N/4 인 부분 배열 4개를 정렬하기 위해 크기 N/8 인 부분 배열 8개를 비교 합니다. 그러면 N/8 * 8 = N 번 비교하게 됩니다!

 

즉 모든 단계에서 N 만큼 비교를 합니다. 그러면 총 몇 단계(트리의 높이)인지만 알면 시간 복잡도를 구할 수 있습니다!

크기가 N → N/2 → N/2^2 → N/2^3 → .... → 1 이 되는 순간이 있을텐테, 어! 이거 저희 배웠었죠? k = log_2N ! 이었죠?

바로 log_2N번 반복하게 되면 1이 됩니다.

 

이걸 수식으로 나타내면 N만큼의 연산을 logN 번 반복한다고 해서

시간 복잡도는 총 O(Nlog_2N) = O(NlogN) 이 된다! 라고 생각할 수 있습니다.

 

배열 정렬하기

https://leetcode.com/problems/sort-an-array/description/

이 코드로 제출하면 무난히 통과함을 확인할 수 있습니다. 시간복잡도의 중요성을 증명하네요.

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


def mergesort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    return merge(mergesort(L), mergesort(R))

 

 

내장함수는 팀정렬(timsort: 삽입정렬과 병합정렬 합쳐서 최적화한 정렬방식)를 사용하여,
내장함수보다는 조금 느리지만
병합정렬도 꽤나 빠른 편이다.

따라서 실무에서는 C언어를 사용하지 않는 이상
보통 내장 함수를 사용한다.

---

 

Heapsort(힙 정렬)

힙이란? 

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

부모와 자식 간의 대소관계가 명확한 트리!

(부모는 항상 자식보다 크거나/ 부모가 항상 자식보다 작거나.)

항상 최대의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 되겠죠!

그러면 힙을 구현하려면 어떻게 해야할까요?
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠!

따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 1     Level 2  # 자식 노드보다 크니까 힙이 맞습니다!


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
   4 2 5     Level 2  # 자식 노드보다 크지 않아서 힙이 아닙니다..!

 

참고로, 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고,

최솟값을 맨 위로 올릴 수도 있습니다!

최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 합니다!

 

최소힙 / 최대힙

• BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않음.
• 계산 편의를 위해 인덱스는 1부터 사용한다. (parent: x, left: 2x, right: 2x+1)

최소힙이나 최대힙이나 시간 복잡도는 같다.

 

최소 힙 - 삽입 시간복잡도

결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있습니다.

완전 이진트리의 최대 높이는 O(log(N)) 이라고 말씀 드렸었죠!

그러면, 반복하는 최대 횟수도 O(log(N)) 입니다.

즉! 최소 힙의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

 

최소 힙 - 추출 시간복잡도

결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있습니다.

완전 이진트리의 최대 높이는 O(log(N)) 이라고 말씀 드렸었죠!

그러면, 반복하는 최대 횟수도 O(log(N)) 입니다.

 즉! 최소 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있습니다.

 

최소 힙 - 구현 (1)

class BinaryMinHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] < self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        smallest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != cur:
            self.items[cur], self.items[smallest] = self.items[smallest], self.items[cur]
            self._percolate_down(smallest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

 

배열 정렬하기

def sorted_by_heap(lst):
    maxheap = BinaryMaxHeap()
    for elem in lst:
        maxheap.insert(elem)

    desc = [maxheap.extract() for _ in range(len(lst))]
    return list(reversed(desc))

 

 

원점에 K번째로 가까운 점

https://leetcode.com/problems/k-closest-points-to-origin/description/

직접 구현 - 1660 ~ 3707ms, 20.0MB

import math


class BinaryMinHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)
        # left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
        parent = cur // 2

        while parent > 0:
            if self.items[cur] < self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        smallest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != cur:
            self.items[cur], self.items[smallest] = self.items[smallest], self.items[cur]
            self._percolate_down(smallest)

    def insert(self, dist):
        self.items.append(dist)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None

        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

# 원점까지 거리 구함
def cal_dist(point):
    # 원점까지 거리 (비교하는 것이므로 굳이 루트를 씌우지 않아도 되긴 함)
    return math.sqrt(point[0] * point[0] + point[1] * point[1])


def k_closest(points, k):
    heap = BinaryMinHeap()
    # 거리의 목록
    dists = []
    for point in points:
        # 거리 계산
        dist = cal_dist(point)
        # min heap 에 넣음 - root는 항상 최소값이 될 것
        heap.insert(dist)
        # point[i] = dist[i]
        dists.append(dist)

    # k번째로 가까운 거리는, (min) heap에서 k 만큼 뽑으면(extract) k번째 가까운 순으로 정렬됨
    # [-1]: 가장 마지막 값(루트)
    kth_dist = [heap.extract() for _ in range(k)][-1]
    
    # points[idx] 의 거리는 dists[idx]
    # 거리의 값이 기준값보다 작거나 같은 경우에만 points 배열에 담음
    return [points[idx] for idx, dist in enumerate(dists) if dist <= kth_dist]

 

 

내장 heapq - 736 ~ 1148ms, 19.7MB

import heapq

def k_closest_builtin(points, k):
    dists = []
    heap = []
    for point in points:
        dist = cal_dist(point)
        heapq.heappush(heap, dist)
        dists.append(dist)

    kth_dist = [heapq.heappop(heap) for _ in range(k)][-1]
    return [points[idx] for idx, dist in enumerate(dists) if dist <= kth_dist]