🔥 TIL - Day 34

몇 번을 해도 매번 초면같은 정렬 알고리즘... 언젠간 익숙해지겠지..

최근 몇 개의 면접수기에서 래퍼런스 없이 구현할 수 있는 정렬 알고리즘을 묻는 경우를 봤다. 나는 뭐라고 대답할까? 버블, 선택, 삽입 정도..?

초라하다... 다시 알아보고 더 .. 더 알아보자..

📌 삽입정렬

삽입정렬은 앞으로 나아가면서 점점 정렬 해가는 방식이다.

첫번째 반복에서 두번째 요소의 자리를 잡는다.
첫번째와 두번째를 비교!

두번째 반복에서 세번째 요소의 자리를 잡는다.
세번째부터 두번째 첫번째 쭉 비교하며 왼쪽의 값이 더 클 때까지 이동하면서 자리를 바꾼다.

이를 반복하면 n번 반복마다 n+1개의 요소를 정렬할 수 있다.

시간복잡도는 버블정렬과 동일한 O(N) 이지만 자리를 잡았을 때 break 문으로 탈출할 수 있기 때문에 버블정렬 보다는 좋은 성능을 갖는다.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        min_idx = i
        for j in range(i):
            if arr[i-j] < arr[i-j-1]:
                arr[i-j], arr[i-j-1] = arr[i-j-1], arr[i-j]
            else:
                break

📌 병합정렬

병합정렬은 두 부분으로 나뉜다.
분할하는 부분과 병합 하는 두 부분이다.

먼저 분할하는 부분을 살펴보자.
정렬하고자 하는 배열을 매개변수로 받고 계속 절반씩 잘라가며 정렬된 배열을 얻을 때까지 반복한다. 여기서 얻을 수 있는 정렬된 배열은 길이가 1인 배열이다.

배열의 길이가 1이 될 때까지 분할 하는 것을 목표로 하는 것이다.

def devide(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left_arr = devide(arr[mid:])
    right_arr = devide(arr[:mid])

이제 분할된 배열을 병합할 차례이다.
병합하는 부분을 살펴보자.

매개변수로는 분할된 왼쪽부분과 오른쪽부분 배열을 받는다.
각 배열은 독립적인 인덱스(left_idx, right_idx)를 갖고 서로 현재 인덱스를 비교하며 더 작은 값을 기준으로 병합한다 (오름차순)

def merge(left, right):
    merge_list = []
    left_idx = 0
    right_idx = 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merge_list.append(left[left_idx])
            left_idx += 1
        else:
            merge_list.append(right[right_idx])
            right_idx += 1

    if left_idx < len(left):
        for i in range(left_idx, len(left)):
            merge_list.append(left[i])
    else:
        for i in range(right_idx, len(right)):
            merge_list.append(right[i])
    return merge_list

전체코드

def devide(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n // 2
    left_arr = devide(arr[mid:])
    right_arr = devide(arr[:mid])

    return merge(left_arr, right_arr)

def merge(left, right):
    merge_list = []
    left_idx = 0
    right_idx = 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merge_list.append(left[left_idx])
            left_idx += 1
        else:
            merge_list.append(right[right_idx])
            right_idx += 1

    if left_idx < len(left):
        for i in range(left_idx, len(left)):
            merge_list.append(left[i])
    else:
        for i in range(right_idx, len(right)):
            merge_list.append(right[i])
    return merge_list