Processing lesson(9) ソートアルゴリズム

Learning Objectives

Note

教材を使用される方は、“lesson資料のご利用について”のご一読をお願いします。

線形探索、二分探索について理解し、計算量を算出してみる
ソートアルゴリズムについて異なる複数の方法を理解し、動かしてみる

アルゴリズムの重要性

日本科学未来館　企画・政策フカシギの数え方

アルゴリズムは劇的に処理の効率に影響する

探索の方法（単純な例で比較）

Ref: CodeZine記事「アルゴリズムを勉強するなら二分探索から始めよう！『なっとく！アルゴリズム』より」渡部拓也　[著]2017/02/08

線形探索

先頭から順に検索対象の値を探す

線形探索

二分探索

対象の中央の値を見て、検索したい値と比較することを繰り返す対象がソート済みのデータであることが前提

二分探索

計算量について

最悪の場合、合計で何回計算しなければならないかを考える
オーダー記法で表す。“n個のデータに対して(係数なしで考えた場合に)何度計算しなければならない？
線形探索　O(n)
二分探索　O(log n)
Refs: Qiita記事「計算量オーダーの求め方を総整理！〜どこから log が出て来るか〜」@drken　2020年08月07日に更新

問題１

1-1) 128個の名前が含まれたソート済みのリストに対して、二分探索を使って名前を探す場合、ステップ数は最大でいくつになるか。
1-2) 1のリストが２倍（256個の名前が含まれたソート済みリスト)になった場合に、ステップ数は最大でいくつになるか

問題１答え

1-1) 7回　　
1-2) 8回

問題２

2-1) 10個の名前が含まれたソート済みのリストに対して、二分探索を使って名前を探す場合、ステップ数は最大でいくつになるか

ソートアルゴリズム

配列の中身を並べ替えるためには、どのようにデータを操作すればいいだろう？

選択ソート

データ列の先頭から順に、一番小さいものを探索する。
未整列のデータから最も小さいものを探索し、整列済みのデータに加えることを繰り返す。

未整列のデータ列を全て探し、最も小さいデータを見つける

単純選択ソートのフローチャート

Ref: ソースコード探検隊: 選択ソート

マージソート

データ列をデータ個数に分割する。
分割したものを整列しながら順に併合（マージ）する。

最も小さい単位までデータ列を分割する

ソートしながらデータ列を併合する

→ 小分けにしたデータの単位で整列することで、少ない手順でソート列を作る

Refs: ソースコード探検隊: マージソート

動かしてみよう

1000個の0から500までのランダムなデータをソートした場合のデータの比較回数

選択ソート: 比較約499500回
マージソート：分割 999回、マージ約8146回、比較8702回

データの数を変更すると、計算回数がどうなるか確認してみよう

汎用的な意味での計算量はアルゴリズムに左右されるが、どのアルゴリズムを選ぶかはcase by case. -

対象とするデータのサイズ、分散、データ構造
消費するシステム資源（メモリのサイズなど）
プログラミング言語（サポートするデータ構造、ライブラリ）、ソートアルゴリズムはプログラムライブラリの中に隠蔽されている
- 配列やリストを並べ替えるライブラリは提供されている(array=sort(array);)

選択ソート

1000個のデータを選択ソートで並べ替える

joho_sort_simple_selection.pde

final int NUM_DATA=1000;
final int MAX_DATA = 500;
final int DIAMITER=5;
// データを格納する配列
int[] nums;
int i = 0; // draw用の変数(ソート回数)。drawする度にカウントアップ
int compare_count = 0; // 比較回数

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(1000,500); //MUM_DATAを変更したら1つめの引数を変更する
  background(0,0,0);
  //丸の色
  stroke(0,255,0);
  textSize(50);
}

void loadData(){
  nums = new int[NUM_DATA]; // データ個数分のint型配列を作成
  for(int k=0; k<NUM_DATA; k++){
  // MAX_DATAまでのランダムな整数を配列に格納
  nums[k]=int(random(MAX_DATA));
  }
}

// 単純選択ソートの関数
// draw処理（frame回数/秒ごとに実行されるループ)の中で呼ばれる関数
void onePassOfSelectionSort(int i){
  int current = i;
  // 1つ次のデータから末尾までのデータを順に探して、今のデータを比較する
  for(int compare = i + 1; compare < NUM_DATA; compare++){
    compare_count++; // もし比較対象が今のデータよりも小さかったら　
    if(nums[compare] < nums[current]){
      current = compare;
    }
  }
  int org_data = nums[i]; // オリジナル(i番目のデータ)の要素を取得
  nums[i] = nums[current]; // i番目の位置にcurrent番目(最も小さい値)の要素をセット
  nums[current] = org_data; // current番目の位置にオリジナル(i番目)の要素をセット
}

// draw()は60fpsで繰り返し実行される
void draw(){
  // 1drawごとに0から対象データの数まで、順に処理する
  if (i < NUM_DATA - 1){
    // i番目の数に対する単純選択ソート
    onePassOfSelectionSort(i);
<code>    //結果をプロット</code>
  <code>  clear(); // 都度書き直すためクリアする</code>
  <code>  //描画のためのループ</code>
  <code>  for (int k=0; k < nums.length; k++) {</code>
  <code>    ellipse(k,nums[k],DIAMITER, DIAMETER);</code>
 <code>    }</code>
  <code>//次のデータへ（次のdraw処理へ</code>)
   <code>i++;</code>
  }
  text("Compare: "+ compare_count, 50,50);
}

マージソート

1000個のデータをマージソートで並べ替える

joho_sort_merge.pde

final int NUM_DATA=1000;
final int MAX_DATA = 500;
final int DIAMITER=5;
int[] input_nums; //入力データ
int[] result_nums; // ソート済みデータ
int compare_count = 0; //比較回数
int devide_count = 0; //配列の分割回数
int merge_count = 0; //配列のマージ回数
int i = 0; // draw用の変数。drawする度にカウントアップ

void setup(){
  //ランダムなデータを配列"input"に読み込む
  loadData();
  //ディスプレイウインドウの設定
  size(1000,500);// MUM_DATAを変更したら1つめの引数を変更する
  background(0,0,0);
  textSize(50);
  // CREATING A MERGESORT OBJECT
  MergeSort ms = new MergeSort(input_nums);
  ms.SORT_EXECUTE();
  // GRAB THE RESULTS
  result_nums = ms.RESULT();
  stroke(0,255,0);
}

// マージソートを行うクラス
public class MergeSort {
  // Original code written by Mitko Nikov, revised by tatoflam
  // FREE TO BE USED AND MODIFIED
  // クラス変数
  private int[] input_array; // n オリジナルデータ
  private int[] array; // n ソート済みデータ
  private int[] arrayIndexes; // ソート済みデータのオリジナルデータのインデックス
  private int[] tempFirst; // n / 2 memory
  private int[] tempSecond; // n / 2 memory
  // IF TRUE, COMPARE IN INCREASING ORDER
  private boolean Compare;
  // IN THIS CLASS, MERGE SORT IS IMPLEMENTED WITH TOP-DOWN APPROACH
  MergeSort(int[] input) {
  // BY DEFAULT THE COMPARE BOOL IS TRUE(INCREASING ORDER)
  Compare = true;
  input_array = input;
  SORT_INIT();
}

MergeSort(int[] input, boolean increasing) {
  Compare = increasing;
  input_array = input;
  SORT_INIT();
}
void SORT_INIT() {
  int is = input_array.length;
<code>  // CREATING THE PUBLIC ARRAYS</code>
  <code>array = new int[is];</code>
  <code>arrayIndexes = new int[is];</code>
<code>  tempFirst = new int[is / 2 + 2];</code>
  <code>tempSecond = new int[is / 2 + 2];</code>
  <code>// COPY THE INPUT ARRAY </code>
  <code>// CREATE THE ARRAY OF INDEXES</code>
  <code>for (int i = 0; i < is; ++i) { </code>
    <code>array[i] = input_array[i]; </code>
    <code>//ソート前の色</code>
    <code>stroke(255,0,0);</code>
    <code>arrayIndexes[i] = i;</code>
    <code>ellipse(i,array[i],DIAMITER,DIAMITER);</code>
  <code>}</code>
}

void SORT_EXECUTE() {
  // CALL MERGESORT FUNCTION
  int is = input_array.length;
  MERGESORT(0, is - 1);
<code>  // USING THE SORTED INDEXES, SORT THE ARRAY</code>
  <code>for (int j = 0; j < is; ++j) {</code>
<code>    array[j] = input_array[arrayIndexes[j]];</code>
  <code>}</code>
}

// THIS IS A RECURSIVE FUNCTION
private void MERGESORT(int start, int end) {
  if (start < end) {
  int middle = (start + end) / 2;
  // println("DEVIDE " + devide_count);
  devide_count++;
  MERGESORT(start, middle);
  MERGESORT(middle + 1, end);
  MERGE(start, middle, end);
<code>  }</code>
}

private void MERGE(int start, int middle, int end) {
  // COPYING THE ARRAY TO TWO TEMP ARRAYS
  for (int i = start; i <= middle; ++i) {
    tempFirst[i - start] = arrayIndexes[i];
<code>    int secondPos = middle + (i - start) + 1;</code>
  <code>  if (secondPos <= end) {</code>
  <code>    tempSecond[i - start] = arrayIndexes[secondPos];</code>
<code>    } </code>
  <code>}</code>
  <code>int INF = Compare ? 99999999 : -99999999; </code>
  <code>tempFirst[middle - start + 1] = INF; </code>
  <code>tempSecond[end - middle] = INF;</code>
  <code>// MERGE</code>
  <code>int i = 0, j = 0;</code>
  <code>for (int k = start; k <= end; ++k) {</code>
 <code>   if (tempSecond[j] == INF) {</code>
      <code>arrayIndexes[k] = tempFirst[i];</code>
      <code>i++; </code>
      <code>merge_count = merge_count + i;</code>
      <code>continue;</code>
  <code>   } if (tempFirst[i] == INF) {</code>
  <code>     arrayIndexes[k] = tempSecond[j];</code>
       <code>j++;</code>
       <code>merge_count = merge_count + j;</code>
       <code>continue;</code>
    <code>} if (COMPARE( array[ tempFirst[i] ], array[ tempSecond[j] ] )) {</code>
<code>      arrayIndexes[k] = tempFirst[i];</code>
      <code>i++; </code>
    <code>} else { </code>
      <code>arrayIndexes[k] = tempSecond[j];</code>
     <code> j++; </code>
    <code>} </code>
  <code>}</code>
}

private boolean COMPARE(int a, int b) {
  compare_count++;
  if (Compare) {
    // SORTING IN INCREASING ORDER
    if (a <= b) return true;
  } else {
   // SORTING IN DECREASING ORDER
   if (a >= b) return true;
  }
  return false;
}

// RETURNS THE SORTED ARRAY
int[] RESULT() {
  return array;
}
// RETURNS THE ORIGINAL INDEXES
// OF THE SORTED ELEMENTS
int[] RESULTINDEXES() {
  return arrayIndexes;
}
}

void loadData(){
  input_nums = new int[NUM_DATA];
  for(int k=0; k<NUM_DATA; k++){
    input_nums[k]=int(random(MAX_DATA));
  }
}

// draw()は60fpsで繰り返し実行される
void draw() {
  // 1drawごとに0から対象データの数まで、順に処理する
  if (i < NUM_DATA - 1){
    //結果をプロット
<code>    ellipse(i,result_nums[i],DIAMITER,DIAMITER);</code>
   <code> i++;</code>
  }
  text("Devide: "+devide_count, 50,50);
  text("Merge: "+merge_count, 50,100);
  text("Compare: "+compare_count, 50,150);
}

Processing lesson(9) ソートアルゴリズム

Learning Objectives

アルゴリズムの重要性

探索の方法（単純な例で比較）

線形探索

二分探索

計算量について

問題１

問題１ 答え

問題２

ソートアルゴリズム

選択ソート

マージソート

動かしてみよう

選択ソート

joho_sort_simple_selection.pde

マージソート

joho_sort_merge.pde

問題１答え