DA:sort

バブルソート

import random

def bubblesort(numbers):
    flag = True
    while flag:
        flag = False
        for i in range(len(numbers) - 1):

            ### ここを埋める ###

    return numbers

numbers = [random.randint(1,30) for i in range(30)]
print('整列前:', numbers)
numbers = bubblesort(numbers)
print('整列後:', numbers)

挿入ソート

import random

def insertionsort(numbers):
    for i in range(1, len(numbers)):
        x = numbers[i]
        for j in range(i, 0, -1):

            ### ここを埋める ###

    return numbers

numbers = [random.randint(1,10) for i in range(10)]
print('整列前:', numbers)
numbers = insertionsort(numbers)
print('整列後:', numbers)

ヒープソート

ヒープ操作のための関数（push, pop等）は省略しています．また，ヒープソートはその場整列が可能であるが，プログラムを簡単にするためにheapとは別の配列numbersにソートしたものを格納してreturnしている点に注意．

def heapsort():
    N = len(heap)
    numbers = [0 for i in range(N)]
    
    ### ここを埋める ###
    
    return numbers

numbers = [random.randint(1,10) for i in range(10)]
print('整列前:', numbers)

# ヒープを構築
heap = []
for x in numbers:
    ### ここを埋める ###

numbers = heapsort()
print('整列後:', numbers)

クイックソート

クイックソートはその場整列が可能ですが，簡潔にするために外部配列（leftとright）を用いています．leftにはpivot以下のものが，rightにはpivotより大きいものが並びます．最後にleft（再起的にソート済み）, [pivot], right（再起的にソート済み）を連結してreturnします．

import random

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 基準となる値（ピボット）を先頭要素とする

    left = []   # ピボット以下
    right = []   # ピボットより大きい
    for x in arr[1:]:
        if x <= pivot:
            #ここを埋める
        else:
            #ここを埋める

    return quicksort(left) + [pivot] + quicksort(right)

numbers = [random.randint(1, 50) for i in range(20)]
sorted_numbers = quicksort(numbers)

print('元の配列　　：', numbers)
print('ソートした後：', sorted_numbers)