負けてたまるか。

脳トレ、プログラミング、PHP、WEB製作などのメモ

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--.--.-- --:-- | スポンサー広告 | トラックバック(-) | コメント(-) | Edit
整列処理
  • データが規則的に並んでいたほうがプログラムが簡単になるので、データは並び替えて操作することが多いです。
  • データを大きい順、小さい順に並び替えることを整列(ソート)といいます。
  • たとえば、会社であれば、お給料の高い順に並べる。また、学校であれば、出席番号順に並べる、テストの成績順に並べる、といったことに使います。

クイックソートとは?



ランダム配列数のクイックソートの例
  • クイックソートは整列処理のアルゴリズムの一つ
  • いくつかに小さく分割して並び替えする方式(分割統治法
  • 1960年にアントニー・ホーアが開発した
  • 2008年3月現在、一番効率の良いソート方法として知られている
  • 多くのプログラムで利用されている

アルゴリズム:クイックソート
  • まず適当な数(ピボットという)を選択します。
  • ピボットを基準に、左右に分割します。
  • たとえば、ピボットより小さい数は左側、大きい数は右側に2分割していきます。
  • 分割した部分に 1~3 を適用していき、ソートが完了するまで繰り返す。(再帰という)

図解アルゴリズム:クイックソート



左端を親要素(ピボット)とする、
leftにピボットよりも小さい数、r4ightに大きい数を入れる。入れる方法はleft、erightを交換していく。
sっして、ピボットの左側の要素(left)と右側の要素(right)で再帰処理を行いソートを完了させる


スポンサーサイト
| ホーム |

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

最近の記事

月別アーカイブ

タグリスト

ブログ内検索

カテゴリー

RSSフィード

リンク

ブロとも申請フォーム

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。