ソートっていろんなアルゴリズムがありますよね。
今回はそれのいくつかをまとめてみました
バブルソート
バブルソートの仕組みは簡単、前の要素と比較し、前のほうが大きければ互いに交換するだけです。
直感的にわかりやすいのですが、O(N²)というとても遅い速度でしかソートすることができません。
しかし、このアルゴリズムがもとになってできたアルゴリズムがたくさんあります。
シェーカーソート
シェーカーソートは上のバブルソートを改良したものです。
バブルソートは一番後ろに行った後、また前から比較し始めるのですが、それをそのまま逆走する感じで行くことによって速度を速めることができます。
また、1往復したら一番前と一番後ろは確定なので、どんどん比較の範囲が短くなってきます。
けど、このソートも計算量はO(N²)なのであまり早くはありませんが、ほとんどソート済みの物には素早い計算ができます
クイックソート
一般に、今一番早いと言われているアルゴリズムです。
しかし、平均の計算時間はO(N log N)くらいと、とても速いのですが、最大の計算量はO(N²)にもなります。
クイックソートの仕組みは、はじめに基準を決め、それ以下の物を前からさがし、見つかったら後ろから基準以上のものを探します。
それが基準以下のものが基準以上より前にあった場合、この二つを入れ替え、これを基準を変えずに繰り返していき、そうすると基準以下の物が基準以上の物の後ろ側に来ることがあるので、そこで数の大きいグループと数の小さいグループに分けることができるので、それぞれ初めから繰り返していく。というものです。
基準の選び方はデータの最初の要素を基準にしたり、ランダムに選んだり、ランダムで3に選びその平均を基準にしたり、最初の二つの要素のうち、大きい方を基準とするなどのいろいろな決め方があります。
今回はここまで！それではまた来週～