정렬

스파르타코딩클럽 알고리즘 강의

버블정렬

첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료,...,마지막 이전 자료와 마지막 자료 비교

https://gfycat.com/ko/exaltedinconsequentialdwarfrabbit

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

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

bubble_sort(input)

시간 복잡도 O($N^2$)

선택정렬

배열 [4, 6, 2, 9, 1]
선택정렬은 4와 6과 2와 9와 1을 차례차례 비교

1번째 : [4, 6, 2, 9, 1]
             4, 6, 2, 9, 1 중 최솟값 찾기!
2번째 : [1, 6, 2, 9, 4]
                 6, 2, 9, 4 중 최솟값 찾기!                  
3번째 : [1, 2, 6, 9, 4]
                     6, 9, 4 중 최솟값 찾기!
4번째 : [1, 2, 4, 9, 6]
                          9, 6 중 최솟값 찾기!                     

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


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
                min_index = i + j

        array[i], array[min_index] = array[min_index], array[i]
    return array


selection_sort(input)

시간 복잡도 O($N^2$)

삽입정렬

삽입 정렬은 전체에서 하나씩 올바른 위치에 삽입 하는 방식
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식

[4, 6, 2, 9, 1]

1단계 : [4, 6, 2, 9, 1] 
        4는 현재 정렬되어 있음, 6을 받음
        4 < 6 이므로 그대로 둔다.
       [4, 6, 2, 9, 1]

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] 

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


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 array

insertion_sort(input)

시간 복잡도 O($N^2$)
최선의 경우 Ω(N)