名称 | 処理内容 | 計算量 |
バブルソート | 配列の先頭から後ろに向かってスキャンし、隣り合う要素の大小関係が逆である場合は入れ替える。 | O(n^2) |
選択ソート | 未整列の(整列されていない)部分から最小の要素を選び、それを未整列部分の先頭に移動させ、徐々に整列を行っていく。 | O(n^2) |
挿入ソート | 配列の一部を整列済みとし、残りの要素を一つずつ、整列済みの部分の適切な位置に挿入していく。 | O(n^2) |
ヒープソート | insert処理によって探索木を構築し、それに対してremoveMin処理を行っていき、要素を取り出していくことで整列を行う。 | O(nlogn) |
マージソート | データ列を真ん中で半分に分けていき、それぞれの部分列で整列を行った後に合併(マージ)を行っていくことで整列を行う。 | O(nlogn) |
シェルソート | hずつ離れた要素同士で整列を行っていき、hを大きい値から小さい値に変化させてこの処理を繰り返すことで整列を行う。 | O(n^1.5)程度 |
クイックソート | 1つの要素を枢軸として定め、枢軸より小さい要素を左側に、大きい要素を右側に集める処理を繰り返すことによって整列を行う。 | O(nlogn)。 |