[알고리즘] 파이썬으로 정렬 알고리즘 구현하기

파이썬으로 구현한 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬, 쉘 정렬입니다.

1. 선택 정렬(Selection Sort) 오름차순

arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(0, n-1):
    least = i
    for j in range (i+1, n):
        if arr[least] > arr[j]:
            least = j
    arr[i], arr[least] = arr[least], arr[i]
    
print(arr)
# [-1, 0, 1, 2, 3, 4, 4, 5, 7, 88]

2. 버블 정렬(Bubble Sort) 오름차순

arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(n-1):
    for j in range (n-1-i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
    
print(arr)
# [-1, 0, 1, 2, 3, 4, 4, 5, 7, 88]

3. 삽입 정렬(Insertion Sort) 오름차순

arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(1, n):
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key
    
print(arr)
# [-1, 0, 1, 2, 3, 4, 4, 5, 7, 88]

 

4. 병합 정렬(Merge Sort) 오름차순

arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]

def merge(left, right):
    i = 0
    j = 0
    sorted_list = []
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i = i+1
        else:
            sorted_list.append(right[j])
            j = j+1
    while i < len(left):
        sorted_list.append(left[i])
        i = i+1
    while j < len(right):
        sorted_list.append(right[j])
        j = j+1
    return sorted_list
    
def merge_sort(unsorted_list):
    n = len(unsorted_list)
    if n <= 1:
        return unsorted_list
    else:
        mid = n // 2 
        left = merge_sort(unsorted_list[:mid])
        right = merge_sort(unsorted_list[mid:])
        return merge(left, right)
    
print(merge_sort(arr))
# [-1, 0, 1, 2, 3, 4, 4, 5, 7, 88] 

5. 쉘 정렬(Shell Sort) 오름차순

arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]

def shell_sort(unsorted_list):
    gap = len(unsorted_list) // 2
    while gap > 0:
        
        for start in range(gap):
            unsorted_list = gap_insertion_sort(unsorted_list, start, gap)
            
        gap //= 2
    return unsorted_list
        
def gap_insertion_sort(unsorted_list, start, gap):
    
    for i in range(start+gap, len(unsorted_list), gap):
        
        key = unsorted_list[i]
        j = i

        while j>=gap and unsorted_list[j-gap] > key:
            unsorted_list[j]=unsorted_list[j-gap]
            j = j-gap

        unsorted_list[j]=key
    return unsorted_list
    
print(shell_sort(arr))
# [-1, 0, 1, 2, 3, 4, 4, 5, 7, 88]