처음은 quick sort

quick sort는 완벽한 버전은 아니다. pivot 좌우로 크고 작은거 옮기는거 다 한 다음에 리커젼 들어가야되는데 그냥 둘다 한개씩 잡히면 swap해주고 바로 리커젼 들어갔다. 이렇게도 풀리는구나 신기했다.

두번째는 merge sort

예전에는 L = numbers 이런식으로 하면 numbers 원소 바뀌면 L도 바뀌는데 L = numbers[:mid] 이런식으로 하면 안바뀜. 이 원리를 이용해서 mergesort( L), mergesort(R) 이렇게 array를 넣어줘서 풀었는데 그게 어떻게 하는지 생각이 안나고 index로 하는게 좀 더 순리에 맞는거 같아서 이번엔 index를 넣어줬다. right index는 mid + 1로 해줘야 left 부분이랑 안겹치게 sorting되더라. 역시 정렬문제는 디버깅 쓰는게 답이다... 안그러곤 어디서 틀렷는지 못찾겠음...

둘다 알고리즘 자체가 기억이 안나서 예전 코드를 보고 원리를 다시 기억한 다음에 풀었다. 퀵 정렬은 그다지 좋은 알고리즘은 아니어서 연습용으로만 해보라 하더라.

# 퀵 sort 로 풀어본다
# pivot 중심으로 왼쪽의 큰값과 오른쪽의 작은 값을 switch하고 왼쪽부분 recursion, 오른쪽 부분 recursion
def quicksort(left, right):
    if left >= right:
        return

    l_idx = left
    r_idx = right
    m_idx = (left + right)//2
    pivot = numbers[m_idx]

    print(f'a[{left}] ~ a[{right}]: {numbers[left:right+1]}')

    while (l_idx < m_idx and numbers[l_idx] < pivot):
        l_idx += 1
    while (r_idx > m_idx and numbers[r_idx] > pivot):
        r_idx -= 1

    numbers[l_idx], numbers[r_idx] = numbers[r_idx], numbers[l_idx]
    l_idx +=1
    r_idx -=1

    quicksort(left, r_idx)
    quicksort(l_idx, right)

# merge sort 로 풀어본다
# 싹다 1개짜리 원소로 쪼갠뒤 다시 덧붙이는 형식
def mergeSort(left, right):
    if left >= right:
        return
    mid = (left + right) // 2

    mergeSort(left, mid)
    mergeSort(mid +1, right)
    l_idx = left
    r_idx = mid +1
    temp = []

    while l_idx <= mid and r_idx <= right:
        if numbers[l_idx] < numbers[r_idx]:
            temp.append(numbers[l_idx])
            l_idx += 1
        else:
            temp.append(numbers[r_idx])
            r_idx +=1

    while l_idx <= mid:
        temp.append(numbers[l_idx])
        l_idx += 1
    
    while r_idx <= right:
        temp.append(numbers[r_idx])
        r_idx += 1

    for i in range(len(temp)):
        numbers[left + i] = temp[i]