【Python】ソートアルゴリズム

##バブルソート
bubble sort。隣接交換法。単純交換法
隣同士のデ－タを順に比較して交換

####コード

def bubble_sort(buff):
    change = True
    while change:
        change = False
        for i in range(len(buff) - 1):
            if buff[i] > buff[i + 1]:
                buff[i], buff[i + 1] = buff[i + 1], buff[i]
                change = True
    return buff

print(0,lst)
bubble_sort(lst)
print(lst)

####コード2

def bubble_sort(buff):
    L = len(buff)
    for i in range(L-1):
        for j in range(L-1, i, -1):
            if buff[j] < buff[j-1]:
                tmp = buff[j]
                buff[j] = buff[j-1]
                buff[j-1] = tmp
                
print(0,lst)
bubble_sort(lst)
print(lst)

##シェーカーソート
Shaker sort
1パスごとに処理の方向を切り替えバブル・ソート

####コード

#シェーカーソート
def shaker_sort(buff):
    low = 0
    high = len(buff) - 1
    j = -1
    while low < high:
        for i in range(low, high):
            if buff[i] > buff[i + 1]:
                temp = buff[i]
                buff[i] = buff[i + 1]
                buff[i + 1] = temp
                j = i
        high = j
 
        for i in range(high, low, -1):
            if buff[i - 1] > buff[i]:
                temp = buff[i - 1]
                buff[i - 1] = buff[i]
                buff[i] = temp
                j = i
                n=n+1
                print(n,lst)  
        low = j

print(0,lst)
shaker_sort(lst)
print(lst)

##選択ソート
MinimumSort。最小値ソート。単純選択法。セレクションソート
最小(または最大)の値を取り出して先頭におく(最後におく)

####コード

def select_sort(buff):
    L= len(buff)
    for i in range(L - 1):
        min = buff[i]
        nn = i
        for j in range(i + 1, L):
            if buff[j] < min:
                min = buff[j]
                nn = j
        buff[nn] = buff[i]
        buff[i] = min

print(0,lst)     
select_sort(lst)
print(lst)

##挿入ソート
insertion sort。単純挿入ソート
置き換えではなく、挿入してそれ以降の要素をずらす

####コード

#挿入ソート
def insert_sort(buff):
    L = len(buff)
    for i in range(1, L):
        temp = buff[i]
        j = i - 1
        while j >= 0 and temp < buff[j]:
            buff[j + 1] = buff[j]
            j -= 1
        buff[j + 1] = temp

print(0,lst)   
insert_sort(lst)
print(lst)

##シェルソート
shell sort。カクテルソート
挿入ソートを改良
一定間隔だけ離れたデータ同士を比較し、徐々に比較し間隔を狭めながらソートを繰り返す

####コード

def shell_sort(buff):
    L = len(buff)
    gap = int(L / 2)
    while gap > 0:
        for i in range(gap, L):
            temp = buff[i]
            j = i - gap
            while j >= 0 and temp < buff[j]:
                buff[j + gap] = buff[j]
                j -= gap
            buff[j + gap] = temp
        gap= int(gap/2)

print(0,lst)
shell_sort(lst)
print(lst)

##クイックソート
quick sort。スタックソート
データから基準値で２分割し、分割されたデ－タ列に対しても、同様な分割を繰り返す

####コード

def quick_sort(buff):

    L=len(buff)
    if L < 2:
        # 1. 走査する配列長が0か１の場合戻る。
        return buff

    # 2. 走査する範囲の中央の要素をピボットとして選ぶ。
    pivot = math.floor(L/2)
    pivot_height = buff[pivot]
    left = 0
    right = len(buff) - 1

    while(left < right):
        # 3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。
        while(buff[left] < pivot_height):
            # 左側の基準値より大きい位置まで移動
            left += 1
        while(buff[right] > pivot_height):
            # 右側の基準値より小さい位置まで移動
            right -= 1

        if (left < right):
            # leftがrightを超えていない場合、leftとrightを交換
            buff[left], buff[right] = buff[right], buff[left]
            print(buff, pivot_height)
        else:
            break
    # 4. 左右２つに配列を分割してこの関数を再帰的に繰り返す。
    buff[:left] = quick_sort(buff[:left])      # ピボットの左側をクイックソート
    buff[left+1:] = quick_sort(buff[left+1:])  # ピボットの右側をクイックソート
    return buff

print(0,lst)
quick_sort(lst)
print(lst)

##マージソート
merge sort。分割併合法
データを細かい単位に分割して小さい単位でソートし
整列済みのデ－タ列を昇順、あるいは降順に併合する

####コード

def merge_sort(buff):
    if len(buff) <= 1:
        return buff

    mid = len(buff) // 2
    # ここで分割を行う
    left = buff[:mid]
    right = buff[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)

def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

lst=merge_sort(lst)
print(lst)

##ヒープソート
heap sort
選択ソートを改良
部分順序木のデータ構造を配列に置き換える

####コード

def heap_sort(buff):
    i = 0
    L = len(buff)

    while(i < L):
        # ヒープを構成
        upheap(buff, i)
        i += 1

    while(i > 1):
        # ヒープから最大値を取り出し
        i -= 1
        tmp = buff[0]
        buff[0] = buff[i]
        buff[i] = tmp

        # ヒープの再構成
        downheap(buff, i-1)

# buff[n]をヒープ構成部(0～n-1)の最適な位置へ移動
def upheap(buff, n):
    while n != 0:
        parent = int((n - 1) / 2)
        if buff[n] > buff[parent]:
            # 親より大きな値の場合親子の値を交換
            tmp = buff[n]
            buff[n] = buff[parent]
            buff[parent] = tmp
            n = parent
        else:
            break

# ルート[0]をヒープ(0～n)の最適な位置へ移動
def downheap(buff, n):
    if n == 0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # buff[n]の子要素
        if child > n: break
        if (child < n) and buff[child] < buff[child + 1]:
            child += 1
        if buff[parent] < buff[child]: # 子要素より小さい場合スワップ
            tmp = buff[child]
            buff[child] = buff[parent]
            buff[parent] = tmp
            parent = child; # 交換後のインデックスを保持
        else:
            break

print(0,lst)     
heap_sort(lst)
print(lst)

##パンケーキソート
Pancake sorting
先頭から何番目かまでをひっくり返す最小の手数を求める問題

####コード

def pancakesort(buff):
    L=len(buff)

    for size in range(L, 1, -1):
        maxindex = max(range(size), key=buff.__getitem__)
        if maxindex+1 != size:
            # This indexed max needs moving
            if maxindex != 0:
                # Flip the max item to the left
                buff[:maxindex+1] = reversed(buff[:maxindex+1])
            # Flip it into its final position
            buff[:size] = reversed(buff[:size])

print(0,lst)
pancakesort(lst)
print(lst)

##基数ソート
バケットソートの変形

####コード

mask = 0xff
size = 255
 
def radix_sort(buff):
    L = len(buff)
    tmp = [None for _ in range(L)]
    for bit in range(0, 32, 8):
        count = [0 for _ in range(size+1)]
        for i in range(L):
            count[(buff[i]>>bit) & mask] += 1
        for i in range(size):
            count[i+1] += count[i]
        for i in range(L-1, -1, -1):
            count[(buff[i]>>bit) & mask] -= 1
            tmp[count[(buff[i]>>bit) & mask]] = buff[i]
        for i in range(L):
            buff[i] = tmp[i]

print(0,lst) 
radix_sort(lst)
print(lst)

##コームソート
Comb sort
バブルソートを改良
離れた要素同士を比較して交換し、徐々に比較する距離を縮める

####コード

def comb_sort(lst):
    # ギャップの計算に使うための初期値
    gap = len(lst)

    swap_occurred = False

    while gap > 1 or swap_occurred:
        swap_occurred = False
        gap = int(gap / 1.3)
        if gap < 1:
            gap = 1
        i = 0
        L = len(lst)
        while i+gap < L:
            if lst[i] > lst[i+gap]:
                lst[i], lst[i+gap] = lst[i+gap], lst[i]
                swap_occurred = True
            i += 1
        
print(0,lst)    
comb_sort(lst)
print(lst)

##カウントソート
分布数えソート。Distribution Counting Sort

####コード

def count_sort(buff):
    max_num = max(buff)
    min_num = min(buff)
    count = [0] * (max_num - min_num + 1)
    for ele in buff:
        count[ele - min_num] += 1
    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

print(0,lst) 
lst=count_sort(lst)
print(lst)

#動作テスト

# データ
lst=[10, 6, 2, 4, 9, 1, 8, 3, 5, 7 ]

# データ（整数乱数）
import random
n=100
lst = [random.randint(0, 100) for i in range(n)]

#データ
import random
lst = list(range(10))
random.shuffle(lst)

##時間測定

#パッケージ
import time

#実行前に下記を追加
start = time.time()

#最後に実行時間表示
print("elapsed {} sec.".format(time.time() - start))