1. 버블 정렬

1.1 개념

• (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방법

1.2 예시 코드

• 숫자 array를 오름차순으로 정렬하기
• 4와 6, 6과 2, 2와 9, 9와 1을 비교하여 9가 가장 마지막에 정렬됨
• 4와 6, 6과 2, 2와 1을 비교하여 6이 (마지막-1)번째 정렬됨
• 이렇게 반복한 결과 array는 [1, 2, 4, 6, 9]로 정렬됨.

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    count = 0
    while count < len(array):
        for index in range(1, len(array)):
            if array[index-1] < array[index]:
                continue
            else:
                array[index-1], array[index] = array[index], array[index-1]
        count += 1
    return array


bubble_sort(input)
print(input)  

1.3 시간 복잡도

• 결과: O(N^2)
• 이유: N(while문) N(for문) 1(if문)

2. 선택 정렬

2.1 개념

• 길이가 n인 array에서 k번째 숫자를 k+1번째 ~ n번째 숫자와 비교해 정렬하는 방법

2.2 예시 코드

• 숫자 array를 오름차순으로 정렬하기
• 4를 선택한 후 6, 2, 9, 1을 비교하여 가장 작은 1과 자리를 바꿈 -> [1, 6, 2, 9, 4]
• 6을 선택한 후 2, 9, 4를 비교하여 가장 작은 2와 자리를 바꿈 -> [1, 2, 6, 9, 4]
• 6을 선택한 후 9, 4를 비교하여 가장 작은 4와 자리를 바꿈 -> [1, 2, 4, 9, 6]
• 이렇게 반복한 결과 array는 [1, 2, 4, 6, 9]로 정렬됨.

input = [4, 6, 2, 9, 1]


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

    for i in range(n - 1):  # i = 0 / i = 1
        for j in range(i + 1, n):  # j = 1,2,3,4
            min_num = array[i]  # min_num = 4
            if min_num > array[j]:  # 4 < 4 -> false
                min_num = array[j]  # j=4, min_num = 1
                array[i], array[j] = array[j], array[i]  # array = [1,6,2,9,4]

    return array


selection_sort(input)
print(input) 

2.3 시간 복잡도

• 결과: O(N^2)
• 이유: N(for문) N(for문) 1(if문)

3. 삽입 정렬

3.1 개념

• 전체 array에서 하나씩 올바른 위치에 놓아 정렬하는 방법

3.2 예시 코드

• 숫자 array를 오름차순으로 정렬하기
• 4를 선택, 비교 대상이 없으므로 pass -> [4]
• 6을 선택, 4와 비교, 6이 큼 -> [4, 6]
• 2를 선택, 6을 비교, 2가 작음, 4를 비교, 2가 작음 -> [2, 4, 6]
• 9를 선택, 2,4,6 보다 큼 -> [2, 4, 6, 9]로 정렬됨.

input = [4, 6, 2, 9, 1]


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

    for i in range(1, n):  # 9
        for j in range(i):  # 1
            if array[i - j - 1] > array[i - j]:  # 4 < 6
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array


insertion_sort(input)
print(input)  

3.3 시간 복잡도

• 결과: O(N^2)
• 이유: N(for문) N(for문) 1(if문)
• 개선: 인접한 수보다 크면 그 자리에서 순환 중단(break)

4. 병합 정렬 - merge

4.1 개념

• 두 array를 비교하여 제 3의 array에 작은 수를 넣는 방법

4.2 예시 코드

• 숫자 array1과 array2의 숫자를 오름차순으로 정렬하기
• array_1에서 1을 선택, array_2에서 4를 선택 결과, 1이 작음. sorted_array = [1], array_a에서 2를 선택
• array_1에서 2를 선택, array_2에서 4를 선택 결과, 2가 작음. sorted_array = [1, 2], array_a에서 3을 선택
• array_1에서 3를 선택, array_2에서 4를 선택 결과, 3이 작음. sorted_array = [1, 2, 3], array_a에서 5을 선택
• 남는 부분은 순서 그대로 sorted_array에 넣기
• [1, 2, 3, 5, 4, 6, 7, 8]로 정렬됨.

array_1 = [1, 2, 3, 5]
array_2 = [4, 6, 7, 8]


def merge(array1, array2):
    sorted_array = []

    array1_index = 0
    array2_index = 0

    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array1_index]:
            sorted_array.append(array1[array1_index])
            array1_index += 1
        elif array1[array1_index] > array2[array1_index]:
            sorted_array.append(array1[array2_index])
            array2_index += 1

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


print(merge(array_1, array_1)) 

4.3 시간 복잡도

• 결과: O(N)
• 이유: N(while문) * 1(if문) + 1(if문)