Edited at
移行Day 5

AdventCalendar Day05 [超Ruby入門]


はじめに

本記事は、超Ruby入門5日目の記事です。

コメント頂ける方は、ガイドラインを読んで頂けると幸いです。

ソースコード


目的

基本的なアルゴリズムである、バブルソートの実装方法を理解する。

その後、より高速なソートアルゴリズムであるクリックソートとの計算時間を比較することによって

一つの解法に満足することなく、よりよいプログラムを書くことが重要であることを認識させる。


目標

バブルソートを自分で組むことができるようになる。

クイックソートがなぜ、高速なのかを説明できるようになる。


アルゴリズムとは

初めてこの言葉を聞いた者は、難解なイメージを持つかもしれないが

アルゴリズムとは、単にある問題に対して解を求めるための手段や方法にすぎない。

例えば、一つ100円のりんごを10個買った時の値段を問われたとしたらどのように解を導くだろうか。

100 * 10 = 1000?

もし小学1年生なら

100 + 100 + 100 + 100 + 100 + 100 + 100 + 100 + 100 + 100 = 1000

と答えるのではないだろうか?

決まった解に対する導出手段をアルゴリズムと呼ぶのだ。

コンピュータサイエンスの世界において、アルゴリズムには優劣がある。

一般的により高速、つまり計算時間が短い方が良いアルゴリズムとされている。

上記の問題に対して、乗算は加法より良いアルゴリズムと言えるだろう。(人間的に)


ソートとは

整列(sorting)とは、データの集合をある一定の規則に従って並び替えることだ。

一般的にソートというと、小さい値から大きい値に並ぶ集合の昇順とその反対である降順のことである。

ソートアルゴリズムには、安定であるものとそうでないものがある。

安定であるソートとは、同一な要素を持つキーの順番がソートの前後で変化しないという特性を持つものである。


バブルソート

バブルソートは最も単純ななソートアルゴリズムだ。手順は以下に示す通りだ。


  1. n番目の要素とn+1番目の要素を比較し、昇順に並び替える場合は、n番目の要素が大きい時に交換を行う。

  2. 1の手順を配列の要素数繰り返す


bubble.c


for(i = 0;i < max_num - 1; i++){
for(j = i; j < max_num; j++){
if(array[i] > array[j]){
swap(&array[i], &array[j]);
}
}
}


クイックソート

クイックソートは、安定でないソートアルゴリズムでありバブルソートより高速である。アルゴリズムを以下の通りだ。


  1. 適当な数(ピボットという)を選択する (今回はデータの総数の中央値とする)


  2. ピボットより小さい数を前方、大きい数を後方に移動させる (分割)


  3. 分割したデータグループに対して1.2をグループの要素数が1つになるまで繰り返す


図で理解を深めたい場合にみるリンク

下記は具体的なクイックソートの実装である。


quick.c


void quicksort(int array[], int left, int right){
int origin_l = left;
int origin_r = right;
int pivot = array[(left + right) / 2];
do{
while(1){
if( array[left] >= pivot){
break;
}
left++;
}
while(1){
if( array[right] <= pivot){
break;
}
right--;
}
if ( left <= right){
swap(&array[left], &array[right]);
left++;
right--;
}
}while( left <= right);

if (origin_l < right){
quicksort(array, origin_l, right);
}
if (left < origin_r){
quicksort(array, left , origin_r);
}
}



計算量

アルゴリズムには良さの判断基準があることは既に述べた。

アルゴリズムの性能を比較するためにO記法(オー記法と呼ぶ)が用いられる。

O記法の直感的な求め方は以下のような手順である


  1. 最大次数の項を選択する

  2. 1の係数を除く

以下にO記法の計算例を示す

プログラム全体のステップ数 = 3logn + 2n => 3logn => logn => 0(logn)\\ 

(nは、データ数)

一般的なオーダは以下のテーブルのようになる(下に行くほど遅い)

記法
名称
アルゴリズムの例

O(1)
定数時間
(整数の)偶奇判別

O(logn)
対数
ソート済み配列における二分探索

O(n)
線形関数
非ソート配列上の探索

O(nlogn)
準線形、線形対数
クイックソート

$O(n^2)$
二乗時間
バブルソート

バブルソート平均計算時間が $O(n^2)$ であることはコードから自明である。

クイックソートでは、分割を行う毎にデータが半分になっていく。そのため分割を行うたびに一回にかかる計算時間が半分になってためバブルソートより早いソートアルゴリズムとなる。

しかし、ピボットをデータグループ要素の中で最大または最小の値を常に選択してしまった場合などは、$O(n^2)$となってしまう。データの並びやピボットの選び方が重要であるということを覚えておくと良い。


演習

各ソートの要素数を変化させ計算時間を計測し、グラフにする

クイックソートが安定でないということを確かめるプログラムを書く


もっと深めたい人

内部ソートと外部ソート

蟻本

Atcoder

計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜


参考文献

クイックソートの考え方は?

[初心者向け] プログラムの計算量を求める方法


時間ができた時にやること


  • 安定ソートの図

  • バブルソートの図

  • クイックソートの図