データ構造とアルゴリズム：Bubbleソート

一番左側から、配列の個数分forループを行い、limitまで到達したら再度左に戻ってきて同じ処理を行う。 その際にlimitの位置は1つ左に移動する。

• for j in range(len_numbers - 1)の部分でlimitの移動を再現している。
  • 一番大きい数字は１週目で一番右にくるようになっているのでlimitを設けて一番右端の数値は処理しなくても良いようにする
  • limitを設けることで、無駄なソート処理を行う必要がないので、コードのパフォーマンスが向上する
• for文を２回行って２個目のfor分内で一つ前の配列要素(i)とその一つ後の配列要素を比較して左側(i)の値が小さければ右側の値と入れ替える。
• numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]という処理で入れ替えを行える。

from typing import List

def bubble_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        for j in range(len_numbers - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
    return numbers


if __name__ == '__main__':
    nums = [2, 5, 1, 8, 7, 3]
    print(bubble_sort(nums))
    
[1, 2, 3, 5, 7, 8]

処理時間

bogoソートと比較すると圧倒的に早くなっている。

[1, 2, 4, 5, 6, 8]
0.0003845040009764489

# 配列をランダムに作成したとき
[64, 181, 228, 335, 360, 377, 500, 627, 883, 909]
0.00043242100036877673

ランダムな配列の作り方

これで、0 ~ 1000までのランダムな数字で要素が１０個の配列を作ることができる。

import random
arry = [random.randint(0, 1000) for i in range(10)]