ソート~アルゴリズムのHello World!【株式会社ライトコード】

弊社エンジニアの記事になります。

はじめに

こんにちは。
「ソート」はどの言語においても標準ライブラリなどで高速のアルゴリズムが採用されています。わざわざ実装する機会はなかなかないかと思います。一方でソートのアルゴリズムはアルゴリズム界のHello Worldと言っていいくらい重要です。（素晴らしい記事の受け売りです）
今回はみなさん大好きなソートアルゴリズムについて書こうと思います。
「バブルソート」、「シェルソート」、「マージソート」、「クイックソート」について、そのアルゴリズムと動作をわかりやすく説明することを重視しました（時間計算量や、空間計算量は深入りしません）。
いきなりアルゴリズムのお話ではつかれてしまうので、まずはイメージをつかんでいこうと思います。

質問

50人のエンジニアがいます。誕生日順にならべてください。
条件
- ・同時に比較できるのは２人までとします。
- ・自分で動くのがめんどくさいらしく、あなたが移動してください。

みなさんならどうします？
ここには「sort」メソッドが存在しません。何回も移動させるのは時間がかかってしまいます。なるべく少ない回数で移動させたいです。
そんな状況でソートアルゴリズムを一緒に眺めていきましょう。

バブルソート

まずはバブルソートについて説明していきます。
その名前のように、泡が上に登っていく様子がソートの状態を表しているので名前がついたようです。

直感的にわかりやすいアルゴリズムになります。
誕生日が遅い人（最初は最初の人）がいたらその人を基準にします。比較対象の人が基準の人より遅かったら、その人を基準にして今までの基準の人をそこに入れます。
最後まで行くと一番遅い人が最後にきます。

左から順番に次のものと比較していく。大きかったら順番を入れ替える
一度右まで行くと一番右に一番大きなものが配置される
一番右は「整列済」となるので、次のターンではその一つ前まで比較する
上記を繰り返す

一番最初に検索する際には全てを比較し、だんだんと比較数が少なくなります。
これが大事で「はし」から「はし」までを毎回調べていると時間がかかってしまいます。
一方で最後は検索範囲がせまくなるので高速です。少ないサンプルでは有効なアルゴリズムです。

内部ソート（与えられた配列内でソートをしていくので新たに追加のメモリを使用しない）
安定ソート（同じ値を持つ要素がもともと持っていた相対的な順序をソート後も保持する）
時間計算量 O(n^2) 遅い

などの特徴があります。pythonで実装すると以下のようになります。

import random as rand



rand.seed(0)

n = 100

ar = rand.sample(range(1,n+1),n)



# 昇順にならべる（一番大きいものを右へ

def bubble_sort(ar, n):

    for i in range(n-1, 0, -1):

        for j in range(0, i):

            if ar[j] > ar[j+1]:

                temp = ar[j]

                ar[j] = ar[j+1]

                ar[j+1] = temp



result = []

bubble_sort(ar, n)

print(ar)