알고리즘 - 3주차 [버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬]

 

정렬 : 데이터를 순서대로 나열하는 방법

 

1. 버블 정렬 :

첫번째 자료부터 바로 다음번의 자료와 비교하여 작은 숫자를 앞에 배치하며 앞뒤 자료 두개씩 계속해서 마지막 자료까지 비교해 나간다. 그러면 맨 뒤 자리부터 큰숫자들이 정렬 되어진다.

ex)

 

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


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


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

 

** Swap

두 변수의 값을 교체

>>> a = 3
>>> b = 4
>>> a, b = b, a
>>> print(a)
4
>>> print(b)
3

 

 

2. 선택 정렬 : 

한 사이클에 전체 요소를 탐색하여 최솟값을 찾아 처음 인덱스에 배치하여 탐색 횟수를 1씩 줄이며 사이클을 반복한다.

처음 인덱스부터 하나씩 최솟값을 채워 나간다.

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


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

 

 

3. 삽입 정렬 : 

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성한다.

처음 요소는 하나 이므로 정렬이 완료된 것 이라 보고 두번째 요소부터 왼쪽의 정렬된 배열 부분과 비교하며 반복된다.

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


def selection_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


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

 

 

4. 병합

두개의 배열의 값을 하나씩 비교하여 더 작은 값을 새로운 배열에 하나씩 추가한다.

한 배열이 끝나고 남은 배열은 모든 값을 새로운 배열에 추가한다.

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


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


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8]

 

 

5. 분할 정복 divide and conquer

하나의 문제를 작게 쪼개서 해결한 후 다시 합치면서 문제를 해결하는 방법

동일한 해결법 반복 => 재귀

MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

def merge_sort(array):
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])  # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에
    merge(left_array, right_array)        # 합치면서 정렬

 

 

6. 병합 정렬 :

분할 정복 + 병합

배열의 중간 값으로 두 그룹을 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

 

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


def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = 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_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

 

위 이미지에 진행 순서와 같이 보니 코드 이해가 쉬웠다.

merge_sort 함수에 처음 array 가 들어가고 //2 를 통해 중간 값이 정해진다.

left_array = merge_sort(array[:mid]) 로 인해 중간 값 기준 왼쪽의 배열을 array 값으로 merge_sort 함수를 호출한다.

재기함수 특성상 반복해서 나뉜 배열의 왼쪽의 배열들이 계속해서 나뉘게 되고, 요소가 1개 남을때 까지 반복한다.

배열안의 요소가 1개가 되면 해당 요소가 return 되어 left_array 에 저장이 된다.

호출되었던 라인의 다음 코드 라인 right_array 또한 위의 과정을 반복하고 1개의 요소를 가진 배열이 저장된다.

merge(left_array, right_array) 로 두 요소가 merge함수를 거쳐 정렬되어 합쳐진 값이 return 되고 left_array 에 저장된다.

호출되었던 라인의 다음코드 라인 right_array 로 돌아가서 과정들을 반복하게된다.

 

 

참조: https://bblackscene21.tistory.com/8

[ 알고리즘 공부 ] 합병 정렬(Merge Sort) 알고리즘 - 분할 정복 알고리즘(python, 파이썬)