Bubble sort, selection sort, insertion sort, shell sort, merge sort, quick sort, count sort (Python)

I will summarize the sorting algorithm in Python.

Bubble Sort

Average complexity: $ O (n ^ 2) $ Worst computational complexity: $ O (n ^ 2) $

bubble.py

for i in range(N-1, 0, -1):
    for j in range(i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783238

Selection Sort

Average complexity: $ O (n ^ 2) $ Worst computational complexity: $ O (n ^ 2) $

selection.py

for i in range(N):
    minj = i
    for j in range(i, N):
        if a[j] < a[minj]:
            minj = j

    a[i], a[minj] = a[minj], a[i]

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783283

Insertion Sort

Average complexity: $ O (n ^ 2) $ Worst computational complexity: $ O (n ^ 2) $

insertion.py

for i in range(1, N):
    v = a[i]
    j = i - 1

    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1

    a[j+1] = v

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783260

Shell Sort

As an insertion sort interval column used internally, [Wikipedia article](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82 $ H = \ frac, as in% BD% E3% 83% BC% E3% 83% 88 #% E8% A8% 88% E7% AE% 97% E6% 99% 82% E9% 96% 93) The integer that satisfies {3 ^ i --1} {2} $ is adopted from the largest.

Average complexity: Expected to be $ O (n ^ {1.25}) $ if the above is adopted as the interval sequence Worst Computational Complexity: $ O (n ^ {1.5}) $ if the above is adopted as the interval sequence

shell.py

def insertion_sort(h):
    for i in range(h, N):
        v = a[i]
        j = i - h

        while j >= 0 and a[j] > v:
            a[j+h] = a[j]
            j -= h

        a[j+h] = v

hs = []
h = 1
while h < N+1:
    hs.append(h)
    h = 3 * h + 1

hs.reverse()

for h in hs:
    insertion_sort(h)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783355

Merge Sort

Average complexity: $ O (n \ log n) $ Worst computational complexity: $ O (n \ log n) $

merge.py

INF = 1e10  #Greater than the maximum possible value of an array element

def merge(left, mid, right):
    l = a[left:mid]
    r = a[mid:right]

    l.append(INF)
    r.append(INF)

    i = 0
    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

def merge_sort(left, right):
    if right - left >= 2:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783399

Quick Sort

Average complexity: $ O (n \ log n) $ Worst computational complexity: $ O (n ^ 2) $

quick.py

def partition(left, right):
    x = a[right]
    i = left-1

    for j in range(left, right):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]

    a[i+1], a[right] = a[right], a[i+1]
    return i+1

def quick_sort(left, right):
    if right - left >= 2:
        pivot = partition(left, right-1)
        quick_sort(left, pivot)
        quick_sort(pivot, right)

quick_sort(0, N)

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783489

Counting Sort

** It is also a type of Bucket Sort, Bin Sort **

Average complexity: $ O (n + k) $ Worst computational complexity: $ O (n + k) $

counting.py

K = 100000 #Greater than the number of possible types of array elements

b = [0 for i in range(len(a))]
c = [0 for i in range(K)]

for v in a:
    c[v] += 1

for i in range(K-1):
    c[i+1] += c[i]

for j in reversed(range(N)):
    b[c[a[j]]-1] = a[j]
    c[a[j]] -= 1

#b is a sorted array

verify: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783628