ソートアルゴリズムvol.3【動画#18】マージソート/ソートの計算量/バケットソート/基数ソートの解説

＜ソートアルゴリズムvol.3＞

1. マージソートとは

ソート済配列のマージのアルゴリズムを活用し
配列にソートを行う方法

このアルゴリズムのポイントは
すでに昇順にソート済みの配列どうしをマージするということ

AとBの配列の中身は昇順にソートされている。そのため、最小の値は、A(0番目)またはB(0番目)のどちらかになる。

最終的に、配列Cとなる。

2. ソートの計算量の下限について

アルゴリズムが大小比較に基づいている限り、マージソートよりも最悪計算量が優れたアルゴリズム構築は不可能

＜マージソートの優位性＞
このアルゴリズムの優位性は、あくまで大小比較を前提としたものになるため、それ以外の場合は他にもより速い計算量のアルゴリズムを活用するべき。

3. バケットソートについて

※前提条件：配列の要素は正の整数

① 空のリストからなる配列に、配列の要素と同じ場所にその値を追加していく。

② 配列の要素の番号を空のリストからなる配列の番目に追加していく。

③空のリストからなる配列に追加した要素を先頭から順に取得していく。

＜バケットソートのデメリット＞
要素の最大値が大きいと現実的な計算時間ではなくなる

4. 基数ソートについて

1番低い桁から順番に各桁ごとにソートを行う

＜今回の総まとめ＞
マージソートの特徴、バケットソートの特徴、基数ソートの特徴を理解し、使い分けられるようにしよう

次回、データ構造vol.1 配列について、簡単に整理する。