[내배캠/TIL(8/2)]알고리즘-정렬

day71 TIL

정렬

버블정렬

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

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

선택정렬

선택해서 정렬하는 것을 의미한다. 예를들면 배열에서 가장 작은 값을 골라 맨 앞으로 보내는 정렬을 말한다.

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

삽입 정렬

전체에서 하나씩 올바른 위치에 "삽입" 하는 방식, 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.

def insertion_sort(array):
    for i in range(1, len(array)):
        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

병합 정렬

병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    return merge(merge_sort(left_array), merge_sort(right_array))


def merge(left_array, right_array):
    result = []
    a_pointer = 0
    b_pointer = 0

    while a_pointer < len(left_array) and b_pointer < len(right_array):
        if left_array[a_pointer] <= right_array[b_pointer]:
            result.append(left_array[a_pointer])
            a_pointer += 1
        else:
            result.append(right_array[b_pointer])
            b_pointer += 1
    if a_pointer == len(left_array):
        result = result + right_array[b_pointer:]
    else:
        result = result + left_array[a_pointer:]

    return result