정렬

• 데이터를 순서대로 나열하는 방법
• 데이터를 좀 더 효율적으로 탐색할 수 있게 만듦

1. 버블 정렬

• 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식
• 2차 반복문 -> $O(N^2)$ 시간 복잡도

input = [4, 6, 2, 9, 1]
# 42619  24169  21469  12469

def bubble_sort(array):
    for i in range(len(array) - 1):
        for j in range(len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j+1] = array[j+1], array[j]
                print(j)
    return array

bubble_sort(input)
print(input)

-> 1
3
0
2
1
0
[1, 2, 4, 6, 9]

2. 선택 정렬

• 전체를 보고 선택해서 정렬(최솟값을 찾아)
• 2차 반복문 -> $O(N^2)$ 시간 복잡도

input = [4, 6, 2, 9, 1]
#        0  1  2  3  4
# 16294 - 12694 - 12496 - 12469

def selection_sort(array):
  n = len(array)

  for i in range(n-1):                       # i = 0, array[0] = 4
    min_ind = i
      for j in range(n-i):
        if array[i + j] < array[min_ind]:  # array[2] = 2 < 4 = array[0]   array[4] = 1 < 2 = array[2]
            min_ind = i + j                # min_index = 2                 min_ind = 4
      array[i], array[min_ind] = array[min_ind], array[i]                # [1, 6, 2, 9, 4]
  return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9]

3. 삽입 정렬

• 선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식
• 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
  삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식
• 2차 반복문 -> $O(N^2)$ 시간 복잡도
• else 때문에 시간복잡도가 줄어들 수 있음( $Ω(N)$ )

input = [4, 6, 2, 9, 1]
# 46 비교 - 462 비교 - 2469 비교 - 24691 비교
# 처음 4는 정렬되어있다고 생각

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i-j-1] > array[i-j]:
                array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
            else:
                break
    return


insertion_sort(input)
print(input) # [1, 2, 4, 6, 9]

4. 병합 정렬

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘
• 시간 복잡도는 $O(Nlog_2N) = O(NlogN)$

병합(merge)

• 작은 수 부터 새로운 배열에 추가

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):    # array1의 원소가 모두 추가되면 나머지 array2
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge(array_a, array_b))

분할 정복(Divide and Conquer)

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 예를 들어서 [5, 4] 라는 배열이 있다면
  이 배열을 [5] 와 [4] 를 가진 각각의 배열로 2개의 문제로 분리해서 생각하는 것
  그러면 이 둘을 합치면서 정렬한다면? 결국 전체의 정렬된 리스트가 될 수 있음
• 위 방식으로 하다보면 재귀를 사용하게 됨

MergeSort(시작점, 끝점) 이라 하자
MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
이런식으로 해결 가능

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    return merge(left_array, right_array)

def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result

print(merge(array_a, array_b))