[공부] 내일배움캠프 알고리즘 3주차 정렬

정렬이란?

데이터를 순서대로 나열하는 방법을 의미

---

버블정렬

• n-1번째 자료와 n번째 자료를 비교하여 교환하면서 자료를 정렬하는 방식
• 시간 복잡도: $O(N^2)$

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.

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

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

    for i in range(n-1):

        for j in range(n-1 -i):

            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]

    return

---

선택정렬

• 맨 앞 부터 돌면서 최솟값을 찾아서 위치를 바꿔주며 정렬하는 방식
• 시간 복잡도: $O(N^2)$

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 선택 정렬을 이용해서 정렬하시오.

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

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

    # 총 도는 횟수
    for i in range(n) :

        min_data_index = i     # 최소값 위치를 맨 앞에 숫자의 위치로 초기화        
        for j in range(i, n) :  # 맨 앞부터 끝까지 비교해서 최솟값의 위치찾는 반복문

            if array[j] < array[min_data_index] :
                min_data_index = j 

        array[i], array[min_data_index] = array[min_data_index], array[i]  # 최솟값을 자리에 넣어주기        

    return

---

삽입정렬

• 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식
• 필요할 때만 위치를 변경하므로 더 효율적인 방식!
• 시간 복잡도: $O(N^2)$

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

---

병합정렬

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복

• merge

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) :
        # array2가 남아있다.
        while array2_index < len(array2) :
            array_c.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2) :
        # array1이 남아있다
        while array1_index < len(array1) :
            array_c.append(array1[array1_index])
            array1_index += 1

    return array_c

• merge sort
• 분할 정복의 개념을 적용
• 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략
• 재귀

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)

• 시간 복잡도
  merge 함수는 array1 과 array2 의 길이만큼 정렬하는 것 이므로 $O(N)$,
  merge_sort 함수는 단계마다 $N/2^k * 2$번 비교한다.
  즉, k단계만큼 반복하는데 각각 단계는 $O(N)$의 시간복잡도를 가진다.
  따라서, $log_2N * N$ 이므로, $O(NlogN)$