python 基本的なソートアルゴリズムまとめ(基本情報技術者試験)

半年ぐらい前に書いたソートアルゴリズムです　午後試験でpython選ぶ方は参考にしてください

#insertsort(挿入ソート)
```python:insertsort.py
#挿入ソート
M = [0] * 5
N = 0
J = 0
BUF = [4,2,5,1,3]
for i in range(0,5,1):
    I =0
    while I <=N and M[I] > BUF[i]:
        I = I+1
    J = N
    while J >= I:
        M[J] =M[J-1]
        J = J-1
    M[I] = BUF[i]
    N = N + 1
print(M)
#結果==[5,4,3,2,1]
```


#bubblesort(バブルソート)
```python:bubblesort.py
A = [4,2,5,1,3,6,8,7,6,]
N =len(A)
for i in range(N,1,-1):

    for k in range(0,i-1,+1):
        if A[k] > A[k+1]:
            work = A[k]
            A[k] = A[k+1]
            A[k+1] = work
print(A)
#結果==[1,2,3,4,5,6,7,8]
```
#selctionsort(選択ソート)

```python:selctionsort.py
A =[5,4,2,1,3]
N =4

for I in range(N,0,-1):
    MAX = I
    for J in range(I-1,-1,-1):
        if A[MAX] < A[J]:
            MAX = J
    work = A[I]
    A[I] = A[MAX]
    A[MAX] = work
print(A)
#結果 == [1,2,3,4,5]
````

#shellsort(シェルソート)

```python:shellsort.py
H  = [2,1,3,8,6]

k = (len(H))// 2
u =0
while k != 0:
    s = k
    while s <= len(H)-1:
        u = s - k #
        while u >=0:
            if H[u] > H[u+k]:
                print(H)
                work = H[u]
                H[u] = H[u+k]
                H[u+k] = work
                u = u - k
            else:
                break

        s = s + 1

    k = k // 2
print(H)
#結果==[1,2,3,4,5]
```

#heapsort(ヒープソート)

```python:heapsort.py

#ヒープソート
A = {1:20,2:50,3:10,4:30,5:70,6:40,7:60,8:80}

def INSERT(i):
    num = N # 2
    o = 1
    while  o != 0:
        o = num // 2 # 1
        if A[num] > A[o]:
            work = A[num]
            A[num] = A[o]
            A[o] = work
            num = o
        if A[num] <= A[o]:
            o -=1


    return A


for N in range(2,9,1):
    hoge = INSERT(N)
print ('ヒープ作成結果')
print(hoge)


def heap (hani):#7
    oya = 1
    kodo = oya * 2 #2
    while  kodo < hani: #2>7 再構成ループ
        if kodo+1 <= hani: #3<7
            if hoge[kodo+1] > hoge[kodo]:#60 > 70
                kodo+=1

        if hoge[kodo] > hoge[oya]: #3[60] > 2[70]
            work = hoge[kodo]
            hoge[kodo] = hoge[oya]
            hoge[oya] = work
            oya = kodo
            kodo = oya*2
        elif hoge[kodo] <= hoge[oya]:
             kodo = hani + 1

    return hoge


for s in range(len(hoge),2,-1):
    work = hoge[1]
    hoge[1] = hoge[s]
    hoge[s] = work
    #print(hoge)
    if s > 2:
        hoge= heap(s-1)
print ('ヒープソートを昇順に並び替え')
print(hoge)
#結果 
#ヒープ作成結果
#[1: 80, 2: 70, 3: 60, 4: 50, 5: 30, 6: 10, 7: 40, 8: 20]
#[1: 10, 2: 20, 3: 30, 4: 40, 5: 50, 6: 60, 7: 70, 8: 80]
```
#margesort(マージソート)

```python:margesort.py
 #-*- coding: utf-8 -*-
output =[47,33,68,55,74,89,25,10]

span_size =2 #分割範囲を設定
size = len(output)#outputの要素数を代入
size2 = size // 2
temp = [0]*size2    #入れ替えに使用する配列の大きさを設定

while span_size <= size: #分割範囲のソートが終わったら実行,配列範囲を指定する➀
    span_idx = 0 #初期化  #分割する位置を指定
    write_idx = 0#初期化　#入れ替えの値
    while span_idx < size: #分割の位置を設定②
        a_idx = span_idx #分割した範囲の要素を比較
        b_idx = span_idx + span_size // 2 #分割した範囲内の比較対象を設定

        for i in range(a_idx - span_idx,b_idx - a_idx,1): #入れ替える要素を設定③
            temp[i] = output[i+span_idx]
            #print(temp)
            #print('配列tempに追加')
            a_yet = True
            b_yet = True
        while a_yet == True or b_yet == True:#分割範囲内のソートが終わったらループ終了④
            if b_yet == False or (a_yet == True and b_yet == True and temp[a_idx - span_idx] <= output[b_idx]):#⑤
                #短絡評価

                output[write_idx] = temp[a_idx - span_idx]
        
                a_idx +=1

                if a_idx >= span_idx + span_size // 2:
                    a_yet = False
 
            else:

                output[write_idx] = output[b_idx]

                b_idx +=1

                if b_idx >= span_idx + span_size:#配列tempの要素が全て整列されている時⑥
                    b_yet = False

            write_idx+=1  #代入位置をカウント

        span_idx = span_idx + span_size#ソートが終わったら次の走査範囲へ移動

    span_size = span_size * 2#



print(output)

#結果==[10,25,33,47,55,68,74,89]
```

#クイックソート
```python:quicksoet.py
#クイックソートを用いた配列ソート
#基準値を決めてそれ以上かそれ以下かわけていくソート方法
#再帰関数

A = [2,4,221,5,8,2,9,10]
K = 0
J = 0
def Arrange(A,min,max,pivot):
    L = min
    R = max
    while L <= R:
        tmp = A[L]
        A[L] = A[R]
        A[R] = tmp
        while A[L]< pivot:
            L+=1
        while A[R]>= pivot:
            R -=1

    ret = L
    return ret

def findpivot(A,min,max):
    pivot = A[min]
    K  = min+1
    ret = -1
    found = False
    while K <= max and not found:
         if A[K] == pivot:
             K+=1
         else:
             found = True
             if A[K]> pivot:
                 ret = K
             else:
                 ret = min
    return ret

def quicksort(A,min,max):
    J=findpivot(A,min,max)
    if J > -1:
        pivot = A[J]
        K = Arrange(A,min,max,pivot)
        L = K - 1
        quicksort(A,min,L)
        quicksort(A,K,max)
        return(A)

num = quicksort(A,0,len(A)-1,)
print(num)

#結果[2,2,4,5,8,9,10,221]
```


今思うとスパゲッティコードっすね,,,参考にできなかったらすいません