Sorting 알고리즘 구현 예제 코드 모음집

비전공자 문돌이가 설명하는 파이썬 기본 문법 시리즈에 sorting에 대한 설명은 이미 했었고, 예제 코드도 활용했었습니다. 아래는 지금까지 살펴본 sorting 예제 코드를 모두 모아봤고, 한 눈에 확인할 수 있도록 정리했습니다. 

# Selection Sort
def selectionSort(L: list) -> None:
    # 전체 리스트 훑기
    for i in range(len(L)):
        smallest = i
        
        # 위에서 선택된 원소와 그 다음 위치의 원소들 대소 비교 
        for j in range(i + 1, len(L)):
            if L[j] < L[smallest]:
                smallest = j
        
        # 최종 결정된 최솟값과 i를 비교해서 위치를 swapping
        L[i], L[smallest] = L[smallest], L[i]

---

# Insertion Sort
def insertionSort(L: list) -> None:
    # 리스트 전체 훑기
    for i in range(1, len(L)):

            # 위에서 선택된 원소 인덱스 왼쪽 리스트에서 sorting, 단 오른쪽 인덱스부터 대소 비교 
            for j in range(i, 0, -1):  
                if L[j] < L[j - 1]: 
                    L[j - 1], L[j] = L[j], L[j - 1]  # 인덱스 위치 swapping
                else:
                    break

---

def fast_insertionSort(L: list) -> None:
    for i in range(1, len(L)):
        value = L[i]
        
        # Find the right location for insert
        for j in range(i-1,-1,-1):
            if L[j-1] <= value:
                break
                
        # Insert
        del L[i] 
        L.insert(j, value) # j 번째 인덱스에 value 값 추가 -> 원래 j 번째 값은 j+1번째로 밀림 

---

# Merge Sort
def mergeSortHelp(L: list, first: int, last: int) -> None:
    # 리스트 반으로 쪼개기
    if first == last:
        return 
    else:
        mid = first + (last - first) // 2
        mergeSortHelp(L, first, mid) # left sublist
        mergeSortHelp(L, mid + 1, last) # right sublist
        merge(L, first, mid, last) # merge left and right sublist

def merge(L: list, first: int, mid: int, last: int) -> None:
    # 쪼갠 리스트를 다시 합치기
    sub1 = L[first:mid + 1] # 왼쪽 리스트(sublist1)
    sub2 = L[mid + 1:last + 1] # 오른쪽 리스트(sublist2)
    i = j = 0 # sublist1, sublist2 리스트 인덱스 
    k = first # 전체 리스트 인덱스

    # sublist1과 sublist2 대소 비교해서 상위 리스트에 insert
    while i < len(sub1) and j < len(sub2): # 왼쪽, 오른쪽 리스트 크기가 다를 경우, 한쪽 리스트가 먼저 끝나면 while loop 종료
        if sub1[i] <= sub2[j]:
            L[k] = sub1[i]
            i += 1
        else:
            L[k] = sub2[j]
            j += 1
        k += 1

    # 각 sublist는 이미 정렬된 상태로 그대로 붙이면 됨
    if i < len(sub1): # sublist1의 원소가 남아있을 경우
        L[k:last + 1] = sub1[i:]
    elif j < len(sub2): # sublist2의 원소가 남아있을 경우
        L[k:last + 1] = sub2[j:]

def mergeSort(L: list) -> None:
    mergeSortHelp(L, 0, len(L) - 1)

---

# Quick Sort
def pivotSelect(L: list, low: int, high: int) -> None: # 임의의 3개 원소로 중간값 근사화 
    mid = low + high // 2
    if L[low] > L[mid]:
        L[low], L[mid] = L[mid], L[low]
    if L[mid] > L[high]:
        L[mid], L[high] = L[high], L[mid]
    if L[low] > L[high]:
        L[low], L[high] = L[high], L[low]
    return mid # 중간값 리턴

def partition(L: list, low: int, mid:int, high: int) -> int:
    i = low
    j = high
    # left partition 인덱스 i가 right partition 인덱스 j보다 같거나 클 때 while loop 종료
    while i < j:
        # left partition이 비정상적일 때 루프 종료 
        while i <= high and L[i] <= L[mid]:
            i += 1
        # right partition이 비정상적일 때 루프 종료
        while j >= low and L[j] >= L[mid]:
            j -= 1

        # 비정상적인 i, j 위치를 바꿀 차례 
        if i < j:
            L[i], L[j] = L[j], L[i]

    # pivot 위치 확인 -> i보다 왼쪽에 위치하면 left partition / 오른쪽에 위치하면 right partition
    if mid < i:
        i -= 1

    L[mid], L[i] = L[i], L[mid]
    return i

def partitionSort(L: list, low: int, high: int) -> None:
    if low >= high:
        return 
    else:
        pi_idx = pivotSelect(L, low, high) # pick the initial pivot
        pi_idx = partition(L, low, pi_idx, high) # put the pivot at the right location
        partitionSort(L, low, pi_idx - 1) # left partition
        partitionSort(L, pi_idx + 1, high) # right partition

def quickSort(L: list) -> None:
    partitionSort(L, 0, len(L) - 1)

sorting 알고리즘 설명을 보시려면 제 다른 시리즈를 참고해주세요! 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (4)

비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (4)