ソートアルゴリズムまとめ

bubble sort

def bubble_sort(l):
    n = len(l)
    for i in range(n): # i番目のやつを正しくする.
        for j in range(n-1, i, -1): # 後ろから小さいやつを前に持ってくる.
            if l[j] < l[j-1]:
                l[j],l[j-1] = l[j-1],l[j]

最初よく考えずに、for j in range(i, 0, -1)とかしていた. これだと外側のfor文のi番目を正くするっていうのと合わない.

時間計算量: O(n^2)

insertion sort

def insertion_sort(l):
    n = len(l)
    for i in range(n):
        j = i-1
        v = l[i]
        while j >= 0 and l[j] > v:
            l[j+1] = l[j]
            j -= 1
        l[j+1] = v

selection sort

def selection_sort(l):
    n = len(l)
    for i in range(n):
        min_v = float('inf')
        min_index = 0
        for j in range(i, n):
            if min_v > l[j]:
                min_v = l[j]
                min_index = j
        if i != min_index:
            l[i], l[min_index] = l[min_index], l[i]

merge sort

def merge(A,left,mid,right):
    L = A[left:mid] + [1e10]
    R = A[mid:right] + [1e10]
    i = j = 0
    for k in range(left,right):
        if L[i] <= R[j]: #安定なソートにするためにこうする
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return

def mergeSort(A,left,right):
    if left +1 < right:
        mid = (left + right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

#計算量はO(nlogn)
#段がO(logn)で分けられたやつをマージするのに、O(n)かかるので、O(n*logn)

空間計算量はO(n)らしい. なんで？

quick sort

def partition(A,p,r): #ここまではA[r]以下を返す
    i = p-1
    v = A[r]
    for j in range(p,r): #2 4 5 6 4 3 
        if A[j] <= v:
            i += 1
            A[j],A[i] = A[i],A[j]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1        
            
def quickSort(A,p,r): #pからrまでを
    if p < r:
        q = partition(A,p,r)
        quickSort(A,p,q-1)
        quickSort(A,q+1,r)