🐭 이번 주는 뭐 했어?

정렬

알고리즘의 가장 중요한 주제인 정렬은 데이터를 순서대로 나열하는 방법을 의미합니다 정렬은 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문입니다 이번 포스팅에서는 정렬의 종류에는 어떤 것들이 있고 정렬마다 구현하는 방법에 대해 알아보겠습니다

버블 정렬

버블 정렬은 첫 번째 자료와 두 번째 자료와 검사해 조건에 맞게 위치를 변경하고 또 두 번째와 세 번째 자료와 검사하는 식으로 마지막까지 하나씩 교환하면서 자료를 정렬하는 방식입니다

버블 정렬 예시

[3,1,2,4] <= 정렬되지 않은 배열

1단계: [3,1,2,4]
1과 3을 비교하고 1 < 3 이기 때문에 1을 앞으로 보냅니다
[1,3,2,4]

2단계 : [1,3,2,4]
3과 2를 비교하고 2 < 3 이기 때문에 2를 앞으로 보냅니다
[1,2,3,4]

3단계 : [1,2,3,4]
3과 4를 비교하면 3 < 4 이기 때문에 그대로 둡니다

결과 : [1,2,3,4]

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택 정렬

선택 정렬은 모든 자료를 검사해 가장 작은 값을 찾고 맨 앞으로 보냅니다 그 담으로 작은 숫자를 찾고 가장 작은 값의 뒤로 옮깁니다 이 작업을 계속해 마지막으로 남은 자료까지 앞에 놔두면 작은 순서대로 자료가 완성됩니다

선택 정렬 예시

[3,1,2,4] <= 정렬되지 않은 배열

1단계: [3,1,2,4]
4개를 확인해 1이 제일 작은 것을 확인하고 1과 맨 앞자리 3과 교체합니다
[1,3,2,4]

2단계: [1,3,2,4]
맨 앞자리를 제외하고 나머지 3개를 확인해 가장 작은 값을 확인해 2와 그 다음 자리와
교체합니다
[1,2,3,4]

결과: [1,2,3,4]

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

삽입 정렬

삽입 정렬은 모든 상태를 확인하지 않고 미리 정렬된 자료는 놔두고 변경이 필요한 자료만 비교해 필요할 때만 값을 비교해 위치를 변경하므로 더 효율적인 방식으로 사용 가능**합니다

삽입 정렬 예시

[3,1,2,4] <= 정렬되지 않은 배열

1단계: [3,1,2,4]
3이 정렬된 자료이고 그다음 자료를 확인합니다 1 < 3 이기 때문에 1을 앞으로 보냅니다

2단계: [1,3,2,4]
1,3이 정렬된 자료이고 그다음 자료 2를 확인합니다 2 < 3 이기 때문에 2를 앞으로 보냅니다
그렇지만 1 < 2 이기 때문에 놔둡니다

결과: [1,2,3,4]
정렬된 자료이기 때문에 더 이상 진행하지 않습니다

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst


def insertionsort_2(lst):
    for idx in range(1, len(lst)):
        val = lst[idx]
        cmp = idx - 1

        while lst[cmp] > val and cmp >= 0:
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        lst[cmp + 1] = val

    return lst

퀵소트

퀵소트는 분할 정복을 통해 주어진 배열을 정렬하는 알고리즘입니다 특정 기준을 잡고 기준보다
작은 값과 큰 값을 나누고 그사이에 기준에 맞게 이동시켜 정렬된 자료로 만듭니다

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst