shokosブログ

プログラミング

ソートアルゴリズム計画その2.1

今週は2つのソートアルゴリズムを勉強してコードをかきました

ひとつは隣の値と比較して移動していくバブルソート

もうひとつはある値より大きいの、小さいのと区切って、区切ったかたまりでまた区切って…と繰り返していくクイックソート

今回はその計算量のはなし

なにかを作るとき、ゴールは1つでも手段はいろいろあって、
なかにはすごいメモリをくったり計算時間がかかったりするものもある


たとえばバブルソートクイックソートは昇順にするというゴールは一緒でも内部でぜんぜん違う処理を行っています

計算量を出すと
バブルソートは1/2*n(n-1)回
クイックソートはnlog2n回

たとえば1万個のデータを比較するときに
バブルソートは5億回
クイックソートは13万回
相当違う!!自分で計算してびっくりしました!!!



計算量を考えてコードを書くのって、すごく大切なんですね