정렬 알고리즘 코드(python)

import time
import random
import sys
sys.setrecursionlimit(int(1e9))

def bubblesort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1): # 매번 오른쪽부터 큰 값이 정렬됨 -> n-i-1
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return

def improved_bubblesort(arr):
    end_index = len(arr)-1
    while end_index > 0 :
        swap = 0
        for i in range(end_index):
            # 마지막으로 스왑 된 곳까지 정렬 되었다고 판단 가능하므로 좀 더 효율 
            if arr[i] > arr[i+1] :
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swap = i
        end_index = swap
    return

def selectionsort(arr):
    # 매 루프마다 가장 작은 값을 해당하는 위치에 저장하는 식
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return

def insertionsort(arr):
    # 배열에서 두번째 원소부터 왼쪽의 원소들과 비교하며 교환
    for i in range(1,len(arr)):
        for j in range(i,0,-1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    return
    
def improved_insertionsort(arr):
    # 교환 연산을 최소화 하기 위해 하나씩 시프트하고 마지막에 입력
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        while i > 0 and arr[i - 1] > to_insert:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert
    return

def quick_sort(arr,start,end):
    # 피벗을 정하고 피벗과 원소들의 값을 비교하며 교환하는 정렬 알고리즘
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left<=right:
        while left <= end and arr[pivot] > arr[left]:
            left += 1
        while right > start and arr[pivot] < arr[right]:
            right -= 1
        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot]
        else:
            arr[left], arr[right] = arr[right], arr[left]
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)

def pythonic_quick_sort(arr):
    if len(arr) <= 1:
        return arr
        
    pivot = arr[0]
    tail = arr[1:]
    
    left = [x for x in tail if x <= pivot]
    right = [x for x in tail if x > pivot]

    return pythonic_quick_sort(left) + [pivot] + pythonic_quick_sort(right)

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    
    mid = len(arr)//2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])
    
    merge_arr = []
    l, h = 0, 0

    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merge_arr.append(low_arr[l])
            l += 1
        else:
            merge_arr.append(high_arr[h])
            h += 1
    
    merge_arr += low_arr[l:] + high_arr[h:]
    return merge_arr

def improved_merge_sort(arr):
    # 1. 주어진 배열을 쪼갤 수 있을 때 까지 쪼갬 O(logn)
    # 2. 원소 값을 비교하며 병합하며 합침
    def sort(low,high):
        if high - low < 2 :
            return
        mid = (high + low) // 2
        sort(low,mid)
        sort(mid,high)
        merge(low,mid,high)

    def merge(low,mid,high):
        # 원소값을 비교 O(n)
        temp = []
        l, h = low, mid
        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1
        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1
        for i in range(low,high):
            arr[i] = temp[i-low]
    return sort(0,len(arr))

def heapify(arr, index, heap_size):
    largest = index
    left, right = index*2 +1 , index*2 + 2
    if left < heap_size and arr[largest] < arr[left]:
        # left 자식노드가 heap의 범위를 넘어가지 않고, 부모노드보다 크면 변경
        largest = left
    if right < heap_size and arr[largest] < arr[right]:
        # 마찬가지로 가장 큰 값을 가진 노드인지 확인
        largest = right
    if largest != index: # 인덱스 값이 변경되었으면 -> 자식노드중에 큰 값이 있다는 것
        arr[largest], arr[index] = arr[index], arr[largest]
        heapify(arr, largest, heap_size) # 변경 되었으므로 그 아래도 힙성질을 만족하는지 확인

def heap_sort(arr):
    n = len(arr)
    # max heap 만들기
    for i in range(n//2 -1, -1, -1): # 힙 성질에 따라 맨 끝 노드의 부모 노드는 n//2 -1 이다.
        heapify(arr, i, n)
    
    for i in range(n-1, -1, -1): # 인덱스 기준이므로 n-1이 가장 끝 인덱스
        arr[0], arr[i] = arr[i], arr[0] # 루트노드와 현 상태 가장 끝 노드 값 변경
        heapify(arr, 0, i) # 변경한 루트노드 값부터 다시 heap 만족하도록

def counting_sort(arr,digit):
    n = len(arr)
    # 변경된 정렬 값을 유지할 output 리스트
    output = [0] * n
    # 0 ~ 9 까지의 자리수 수를 더할 counting
    counting = [0] * 10

    # 각 배열의 원소의 자리수에 대한 개수를 counting 리스트에 추가
    for i in range(n):
        index = int(arr[i]/digit)
        counting[index % 10] += 1
    
    # 이전 count 값을 차례로 더해주게 되면, 해당 위치까지 몇개의 원소가 있는지 확인 가능
    for i in range(1,10):
        counting[i] += counting[i-1]
    
    # 안정 정렬이므로 리스트 뒷부분 부터 차레로 위치 변경해준다.
    i = n - 1
    while i>=0 :
        index = int(arr[i]/digit)
        # ouput에서 -1 해주는 이유는 counting의 값은 실제 인덱스 값보다 하나 큼
        # ex) n = 10 이라면 counting[9] <- 가장 끝 원소 == 10 실제로 output끝 값은 output[9]
        # 이 부분은 실제로 코드를 한줄씩 디버깅 하거나 직접 적으면서 생각해야 이해 됨
        output[counting[index % 10] - 1] = arr[i]
        counting[index % 10] -= 1
        i -= 1
    # 정렬된 리스트를 실제 리스트와 값 변경
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    # 배열의 최대 값을 기준으로 자리수 비교
    maxValue = max(arr)
    # 일의 자리부터
    digit = 1
    while int(maxValue/digit) > 0 :
        #counting sort
        counting_sort(arr,digit)
        digit *= 10

def count_sort(arr):
    # 최대값까지 저장 할 수 있게 리스트 초기화
    counting = [0] * (max(arr)+1)
    sorted_arr = []
    
    for i in arr:
        counting[i] +=1
    # 해당 인덱스가 카운트 된 만큼 배열에 추가
    for i in range(len(counting)):
        sorted_arr += [i]*counting[i]
    # 원래 배열에 다시 정렬
    for i in range(len(arr)):
        arr[i] = sorted_arr[i]

num_list = list()
for i in range(10000):
    num_list.append(i)
start = time.time()
insertionsort(num_list)
end = time.time()
print(f"best case insertion sort {end - start:.8f} sec")

start = time.time()
improved_insertionsort(num_list)
end = time.time()
print(f"best case improved insertion sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
bubblesort(num_list)
end = time.time()
print(f"bubble sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
improved_bubblesort(num_list)
end = time.time()
print(f"improved bubble sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
selectionsort(num_list)
end = time.time()
print(f"selection sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
insertionsort(num_list)
end = time.time()
print(f"insertion sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
improved_insertionsort(num_list)
end = time.time()
print(f"improved insertion sort {end - start:.8f} sec")

start = time.time()
quick_sort(num_list,0,len(num_list)-1)
end = time.time()
print(f"worst case quick_sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
quick_sort(num_list,0,len(num_list)-1)
end = time.time()
print(f"quick sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
pythonic_quick_sort(num_list)
end = time.time()
print(f"pythonic quick sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
merge_sort(num_list)
end = time.time()
print(f"merge sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
improved_merge_sort(num_list)
end = time.time()
print(f"improved merge sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
heap_sort(num_list)
end = time.time()
print(f"heap sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
radix_sort(num_list)
end = time.time()
print(f"radix sort {end - start:.8f} sec")


random.shuffle(num_list)
start = time.time()
count_sort(num_list)
end = time.time()
print(f"count sort {end - start:.8f} sec")

random.shuffle(num_list)
start = time.time()
num_list.sort()
end = time.time()
print(f"python implement sort {end - start:.8f} sec")