버블 정렬 (Bubble Sort)

• 인접한 두 수를 비교하며 하나씩 정렬해가는 방법 O(n^2)
• 앞에서 부터 시작하여 큰 수를 뒤로 보내고 내림차순으로 완성 될 때 까지 계속 정렬하는 방법

array = [8,4,6,2,9,1,3,7,5]

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

bubble_sort(array)

선택정렬(Selection Sort)

• 리스트를 한바퀴 돌 때 가장 작은 값을 찾아 맨 앞의 값과 교환하는 방식의 정렬
• 앞에서부터 정렬하는 특성을 가지고 있으며 O(n^2) 성능을 가지고 있다.

array = [8,4,6,2,9,1,3,7,5]

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

병합 정렬(Merge Sort)

• 분할 정복, 재귀를 이용한 알고리즘 O(n logn)의 시간 복잡도를 가지고 있다.
• 최소한의 단위까지 반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되고 이 과정에서 2n개의 공간이 필요

[1,4][2,3] (1과2 비교) -> 1 선택, 완성된 배열은 [1]
[4][2,3] (4와2 비교) -> 2 선택, 완성된 배열은 [1,2]
[4][3] (4와3 비교) -> 3 선택, 완성된 배열은 [1,2,3]
[4][] -> 남는 4 선택, 완성된 배열은 [1,2,3,4]

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)

파이썬으로 구현하는 병합정렬(Merge Sort)