# 앞에서부터 인접한 두 숫자를 비교하면서 시작해 숫자를 교체.
def bubble_sort(array):
    n = len(array)
    for pos in range(n - 1):
        for i in range(n - pos - 1):
            print(f"pos:{pos}, i:{i}")
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
        print(array)

# 한 바퀴 돌며 가장 작은 값을 찾아 맨 앞과 교환
def selection_sort(array):
    n = len(array)
    for pos in range(n):
        min_idx = pos
        for i in range(pos + 1, n):
            if array[i] < array[min_idx]:
                min_idx = i
        array[pos], array[min_idx] = array[min_idx], array[pos]
        print(array)

# key값 앞에 있는 원소와 순서대로 비교
def insertion_sort(array):
    n = len(array)
    for pos in range(1, n):
        val = array[pos]
        i = pos - 1
        while i >= 0 and val < array[i]:
            array[i + 1] = array[i]
            i -= 1
        array[i + 1] = val

# 재귀적으로 반으로 쪼개서 하나씩 만든 후, 한개씩 다시 합치는 분할 정복 알고리즘.
def merge_sort(array):
    if len(array) <= 1:
        return array
    # 쪼개는 부분
    mid_idx = len(array) // 2
    left_array = merge_sort(array[:mid_idx])
    right_array = merge_sort(array[mid_idx:])

    # 합치는 부분
    new_array = []
    i = j = 0
    while i < len(left_array) and j < len(right_array):
        if left_array[i] < right_array[j]:
            new_array.append(left_array[i])
            i += 1
        else:
            new_array.append(right_array[j])
            j += 1
    # 합치고 남은 부분 넣기
    new_array.extend(left_array[i:])
    new_array.extend(right_array[j:])
    return new_array

# 기준이 되는 pivot 값을 정한 후 pivot 기준으로 분할, 정렬.
# 피벗보다 작은 요소들은 모두 피벗의 왼쪽, 크면 오른쪽으로 옮김
def quick_sort(array, left, right):
    def _qsort(array, left, right):
        mid_idx = (left + right) // 2
        mid_val = array[mid_idx]
        while True:
            while array[left] < mid_val:
                left += 1
            while array[right] > mid_val:
                right -= 1
            if left >= right:
                return right
            print(f"left: {left}, right: {right}, mid_idx: {mid_idx}")
            print("교체 전 : ", array)
            array[left], array[right] = array[right], array[left]
            print("교체 후 : ", array)
            print('--------')
            left += 1
            right -= 1

    if left < right:
        pivot = _qsort(array, left, right)
        quick_sort(array, left, pivot)
        quick_sort(array, pivot + 1, right)

# 퀵 정렬이 더 빠르지만, 힙 정렬은 최악의 경우에도 𝑂(nlogn)의 시간 복잡도를 보장. (퀵 정렬 최악: O(n^2))
def heap_sort(arr):
    # 부모: a[(i-1)//2], 왼쪽: a[i*2 + 1], 오른쪽: a[i*2 + 2]
    # 1. 최대 힙 트리 (완전 이진트리)로 만드는 과정 
	     # 힙에서 최대값은 루트에 위치한다. 
	     # (모든 subtree를 위해, 그래서 (n - 1) // 2 부터 0 까지 heapify)
    # 2. 힙에서 루트(최대값)를 마지막 node과 switch 
    # 3. 나머지를 다시 힙으로 만든다
    def heapify(arr, idx, heap_size):
        left_idx = idx * 2 + 1
        right_idx = idx * 2 + 2
        largest = idx
        if left_idx <= heap_size and arr[left_idx] > arr[largest]:
            largest = left_idx
        if right_idx <= heap_size and arr[right_idx] > arr[largest]:
            largest = right_idx
        if largest != idx:
            arr[idx], arr[largest] = arr[largest], arr[idx]
            heapify(arr, largest, heap_size)

    n = len(arr)
    for i in range((n - 1) // 2, -1, -1):  # 1.
        heapify(arr, i, n - 1)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 2.
        heapify(arr, 0, i - 1)           # 3.

# Tim Sort 알고리즘: Insertion sort와 Merge sort를 결합하여 만든 정렬
# <https://d2.naver.com/helloworld/0315536>
"""
Insertion sort는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족한다.
이에 따라 Insertion sort의 상수 C를 Ci, 𝑂(𝑛log⁡𝑛) 정렬 알고리즘 중 C 값이 가장 작다고 알려져 있는 
Quick sort의 상수 C를 Cq라 할 때, 작은 n에 대하여 Ci * n^2 < Cq * nlogn이 성립한다. 
즉, 작은 n에 대하여 Insertion sort가 빠르다는 것이다.
이것을 이용하여 전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 
병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.

1. Run 생성 및 정렬
	- 배열을 일정한 크기의 부분 배열(Run)로 분할합니다.
	- 각 Run을 삽입 정렬을 사용하여 정렬합니다.
2. Run 병합
	- 인접한 Run을 병합합니다.
	- 병합할 때는 병합 정렬을 사용합니다
"""

https://medium.com/pocs/locality의-관점에서-quick-sort가-merge-sort보다-빠른-이유-824798181693

병합정렬은 좌우로 계속 움직이면서 정렬한다. 반면, 퀵 정렬은 한정적인 범위에서 데이터들이 움직인다. 그래서 자주 캐시에 있는 페이지들을 바꿀 필요가 없다. 따라서 퀵정렬은 병합정렬보다 더 참조 지역성의 성질을 띠기 때문에 더 빠르다.