Python 정렬 알고리즘 구현

import random
lis=list(range(100))
random.shuffle(lis)
print(lis)

거품 정렬

def bubbleSort(arr):
    for i in range(1,len(arr)):
        for j in range(0,len(arr)-i):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr
print(bubbleSort(lis))

정렬 선택

def selectionSort(arr):
    for i in range(len(arr)):
        temp=i
        for j in range(i,len(arr)-1):
            if arr[temp]>arr[j]:
                temp=j
        arr[i],arr[temp]=arr[temp],arr[i]
    return arr
print(selectionSort(lis))

정렬 삽입하기

def insertionSort(arr):
    for i in range(1,len(arr)):
        for j in range(0,i):
            if arr[i]<arr[j]:
                for k in range(j,i):
                    arr[k],arr[i]=arr[i],arr[k]
    return arr
print(insertionSort(lis))

힐 정렬

import math
def shellSort(arr):
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
print(shellSort(lis))

병합 정렬

# 
def mergeSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    n = n//2
    sub1 = mergeSort(arr[:n])
    sub2 = mergeSort(arr[n:])
    return merge(sub1, sub2)

# 
def merge(sub1, sub2):
    n1 = len(sub1)
    n2 = len(sub2)
    i = 0
    j = 0
    merge = []
    while i < n1 and j < n2:
        if sub1[i] < sub2[j]:
            merge.append(sub1[i])
            i += 1
        else:
            merge.append(sub2[j])
            j += 1
    #  
    while i < n1:
        merge.append(sub1[i])
        i += 1
    while j < n2:
        merge.append(sub2[j])
        j += 1
    return merge
print(mergeSort(lis))

병합 정렬 교체

def MergeSort(arr):
    n = len(arr)
    size = 1 #  
    m = []
    while size <= n:
        for i in range(0, n-size, size+size):
            m = merge(arr[i: i+size], arr[i+size: min(i+size+size, n)]) # min(i+size+size, n) 
            arr[i: min(i+size+size, n)] = m[:] #  merge 
        size += size #  
    return m
    
# 
def merge(sub1, sub2):
    n1 = len(sub1)
    n2 = len(sub2)
    i = 0
    j = 0
    merge = []
    while i < n1 and j < n2:
        if sub1[i] < sub2[j]:
            merge.append(sub1[i])
            i += 1
        else:
            merge.append(sub2[j])
            j += 1
    #  
    while i < n1:
        merge.append(sub1[i])
        i += 1
    while j < n2:
        merge.append(sub2[j])
        j += 1
    return merge
print(MergeSort(lis))

빠른 정렬

def quickSort(arr):
    return helpQs(arr,0,len(arr)-1)
def helpQs(arr,left,right):
    if left>right:
        return
    k=arr[left]
    i=left
    j=right
    while i!=j:
        while arr[j]>k and i<j:
            j-=1
        while arr[i]<=k and i<j:
            i+=1
        if i<j:
            arr[i],arr[j]=arr[j],arr[i]
    arr[left],arr[i]=arr[i],arr[left]
    helpQs(arr,left,i-1)
    helpQs(arr,i+1,right)
    return arr
print(quickSort(lis))