第1部:ソーティングアルゴリズム

選択ソート

選択ソートアルゴリズムは、ソートされていない部分から最小要素を繰り返し見つけ、最初にそれを置くことによって配列をソートします.アルゴリズムは与えられた配列の2つのサブアレイを維持する.

サブアレイは既にソートされている.

未ソートのサブアレイの残り.
選択ソートのすべての反復処理では、ソートされていないサブアレイからの最小要素が選択され、ソートされたサブアレイに移動されます.

import sys
A = [55, 30, 15, 22, 9]
for i in range(len(A):
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j

    A[i], A[min_idx] = A[min_idx], A[i]

print("Sorted Array")
for i in range(len(A))
    print("%d" %A[i])


# Output
Sorted array
9 15 22 30 55

バブルソート

バブルソートは、繰り返しの場合、彼らは間違った順序にしている隣接する要素をスワップで動作する簡単なソートアルゴリズムです.

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

arr = [73, 34, 27, 12, 22, 10, 110]
bubbleSort(arr)
print("Sorted array")
for i in range(len(arr)):
    print("%d", %arr[i])


# Output
Sorted array
10 12 22 27 34 73 110

バブルソートの再帰的なバージョンもあります
再帰的バブルソートを実装するには?
再帰的バブルソートは、パフォーマンスや実装の利点はありませんが、バブルのソートと再帰の理解を確認するには良い質問をすることができます.
再帰アイデア

基本ケース:配列サイズが1ならば、戻ります.

通常のバブルソートの1パスを行います.このパスは現在のサブアレイの最後の要素を修正します.

現在のサブアレイの最後を除くすべての要素について、recur.

def bubble_sort(listx):
    for i, num in enumerate(listx):
        try:
            if listx[i+1] < num:
                listx[i] = listx[i+1]
                listx[i+1] = num
                bubble_sort(listx)
        except IndexError:
            pass
    return listx

listx = [60, 36, 25, 13, 23, 10, 99]
bubble_sort(listx)
print("Sorted array")
for i in range(0, len(listx)):
    print(listx[i], end=' ')


# Output
Sorted array
10 13 23 25 36 60 99

クイックソート

クイックソートは、分割と征服アルゴリズムです.それはピボットとして要素を選び、選ばれたピボットの周りの与えられた配列を分割します.別の方法でピボットを選ぶクイックソートの多くの異なるバージョンがあります.

常にピボットとして最初の要素を選択します.

常にピボットとして最後の要素を選択します.

ピボットとしてランダムな要素を選択します.

ピボットとしてメディアンを選択します.

クイックソートのキープロセスはパーティション()です.パーティションのターゲットは、配列の配列と要素xをピボットとし、ソートされた配列の正しい位置にxを置き、xの前にすべてのより小さい要素を置き、xの後にすべてのより大きな要素を置きます.

def partition(arr,low,high):
    i = (low-1)
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[j], arr[i+1]
    return (i+1)

def quickSort(arr,low,high):
    if low < high:
        pi = partition(arr,low,high)
        quickSort(arr,low,pi-1)
        quickSort(arr,pi+1,high)

arr = [10, 8, 7, 5, 9, 1]
n = len(arr)
quickSort(arr,0,n-1)
print("Sorted array")
for i in range(n):
    print("%d" %arr[i])


# Output
Sorted array
1 5 7 8 9 10

再帰的なクイックソートの実装は、多くの方法で最適化できます.

再帰的なクイックソートの実装では、最後のインデックスをピボットとして使用します.これは、すでにソートされた配列である、すでにソートされた配列で最悪の場合の振る舞いを引き起こします.問題は、ピボットのランダムインデックスを選択するか、パーティションの中間インデックスを選択するか、ピボットのパーティションの最初、中央、最後の要素の中央値を選択することで解決できます.

再帰深さを減らすために、配列のより小さい半分のために最初にrecandして、もう一方へ再帰的に尾呼び出しを使用してください.

挿入ソートは小さなサブアレイに適しています.挿入ソートは、そのような小さな配列の呼び出しに使用できます.

以下は典型的な再帰的なクイックソートの実装です.

def partition(arr,low,high):
    i = (low-1)
    pivot = arr[high]
    for j in range(low,high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

def quickSort(arr,low,high):
    if low < high:
    pi = partition(arr,low,high)
    quickSort(arr,low,pi-1)
    quickSort(arr,pi+1,high)

if __name__ == '__main__':
    arr = [4, 2, 6, 9, 2]
    n = len(arr)
    quickSort(arr, 0, n-1)
    for i in range(n):
        print(arr[i], end=" ")

# Output
2 2 4 6 9

再帰的クイックソートの後述する最適化は、反復バージョンにも適用できます.

パーティション処理は再帰的で対話的に同じです.最適ピボットを選択するのと同じテクニックを反復バージョンにも適用できます.

スタックサイズを小さくするには、最初に小さな半分のインデックスを押します.

サイズが実験的に計算された閾値の下で減少するとき、挿入ソートを使用してください.

def partition(arr,l,h):
    i = (l-1)
    x = arr[h]
    for j in range(l,h):
        if arr[j] <= x:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[h] = arr[h], arr[i+1]
    return (i+1)

def quickSortIterative(arr,l,h):
    size = h-l+1
    stack = [0]*(size)
    top = -1
    top = top+1
    stack[top] = 1
    top = top+1
    stack[top] = h
    while top >= 0:
        h = stack[top]
        top = top-1
        l = stack[top]
        top = top-1
        p = partition(arr,l,h)
        if p-1 > 1:
            top = top+1
            stack[top] = p+1
            top = top+1
            stack[top] = h

arr = [4, 3, 5, 2, 1, 3, 2, 3]
n = len(arr)
quickSortIterative(arr,0,n-1)
print("Sorted array")
for i in range(n):
    print("%d" %arr[i])


# Output
Sorted array
1 2 2 3 3 3 4 5

挿入ソート

挿入ソートは、我々の手でトランプをソートする方法を動作する単純なソートアルゴリズムです.

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
    print("%d" %arr[i])


# Output
5 6 11 12 13

再帰挿入ソートの例
挿入ソートを再帰的に実行する方法
再帰的挿入ソートは、パフォーマンスや実装の利点はありませんが、挿入ソートと再帰の理解を確認するのに良い質問になります.挿入ソートアルゴリズムを詳しく見ると、処理された要素をソートし、挿入された配列に新しい要素を一つずつ挿入します.
再帰アイデア

基本ケース:配列サイズが1またはそれより小さいならば、戻ります.

再帰的に最初のn - 1要素をソートします.

並べ替え配列の正しい位置に最後の要素を挿入します.

def insertionSortRecursive(arr,n):
    if n<=1:
        return
    insertionSortRecursive(arr,n-1)
    '''Insert last elements at its correct position in sorted array'''
    last = arr[n-1]
    j = n-2
    while (j>=0 and arr[j]>last):
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = last

def printArray(arr,n):
    for i in range(n):
        print arr[i],
arr = [12, 11, 13, 5, 6]
insertionSortRecursive(arr,n)
printArray(arr,n)

# Output
5 6 11 12 13

忘れないでくれtelegram community
PS:トップ7のアルゴリズムシリーズのいくつかの部分になるだろう.