Pythonではじめるアルゴリズム入門輪読会 #4

ホッタ @Hotta3216

今日は「Pythonではじめるアルゴリズム入門」輪読会です。今回で4回目！そろそろ大詰めです～ #ノンプロ研 #Python輪読会 pic.twitter.com/iYhl9vRSzT

拡大

hagy4nonpro @hagy4nonpro

まずは挿入ソートから。 #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

トップバッターはこはたさん テーマは「挿入ソート」 #ノンプロ研 #Python輪読会

コリノ @norizou613

「挿入ソート」 トップバッターはこはたさん。 #ノンプロ研 #Python輪読会 pic.twitter.com/awQEyg03eS

拡大

ホッタ @Hotta3216

挿入ソートとは、「未整列なリスト」からデータを１つ取り出して、「整列済みのリスト」の適切な位置に挿入することを繰り返す #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

トランプとか、本棚を並び替えるイメージ #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

挿入ソートのアルゴリズムは、比較的簡単 #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

ソートのアルゴリズムってどの種類も動きを見えるようにしないと分かりづらいですよね #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

ちゃんと if __name__ == '__main__': を入れてるこはた先生 #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

挿入ソートはマンガを並び替えするのと同じような動きをしますね #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

挿入ソートの計算量はデータの並び方によって変わる #ノンプロ研 #Python輪読会

alice @alice37308108

挿入ソート、確かに時間かかりそう。 #ノンプロ研 #Python輪読会

hagy4nonpro @hagy4nonpro

挿入ソートはシンプル。 #ノンプロ研 #Python輪読会

コリノ @norizou613

挿入ソートはプレーンな感じです。 #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

つぎは「バブルソート」 交換ソートというときはこれを指すらしい #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

これもまだそれほどコードは長くない #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

リストの要素を入れ替えるというのが特徴ですかね #ノンプロ研 #Python輪読会

こはた｜Python、GAS勉強中 @kohaku935

バブルソートとは、リストの隣り合ったデータを比較して、大小の順序が違っているときに並び替える方法。 交換ソート＝バブルソート #ノンプロ研 #Python輪読会

コリノ @norizou613

next バブルソート 隣同士で交換するソート おお、交換回数と交換の内容が出力されている #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

これは人が並んで隣の人と背の高さを比べて入れ替わっていって背の順に並び替える感じですかね #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

これも2重ループを使うので計算時間はO(n^2)で、挿入ソートと同じ #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

バブルソートの終盤は交換なしが多くなってきて、無駄が多い なので、効果が行われないケースについては処理を飛ばすことで高速化を図ることもできる #ノンプロ研 #Python輪読会

こはた｜Python、GAS勉強中 @kohaku935

交換するときの実装が、Pythonだと、パック、アンパックが使えるかららく。 #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

打ち切り処理を入れたら処理回数が減った この減り具合は元のデータによるのか #ノンプロ研 #Python輪読会

ホッタ @Hotta3216

既にソート済みのデータが与えられると、計算時間はO(n)になる #ノンプロ研 #Python輪読会