アルゴリズムをはじめよう

「アルゴリズムをはじめよう」を読みながら、中で取り上げられていたものをjavascriptで実装しました。

読んで理解しても実装するとなると、ちょっと分からなくなったりして、ちゃんとわかったようなわからなかったような。もっと違う書き方もできると思うのですけど、とりあえず本のフローチャートに近い形で書くようにしました。とくにクイックソートのあたりとか、whileループの挙動がいまいちちゃんと把握できてない気がします…。

線形探索法（リニアサーチ）

1
2
3
4
5
6
7
8
9
10
11
12
13
const data = 8; // 目的のデータ
const array = [5, 3, 8, 6, 9, 2]; // 探索する配列

function linearSearch(arr) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === data) {
      return `${i}番目の要素が一致`;
    }
  }
  return "見つかりませんでした";
}

console.log(linearSearch(array)); // 2番目の要素が一致

二分探索法（バイナリサーチ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const data = 26; // 目的のデータ
const array = [11, 12, 15, 18, 21, 26, 28]; // 探索する配列

function binarySearch(arr) {
  
  let head = 0; // 探索範囲の先頭
  let tail = arr.length - 1; // 探索範囲の後尾

  while(head <= tail) {
    let center = Math.floor((head + tail) / 2);
    if (arr[center] === data) {
      return `${center}番目の要素が一致`;
    }
    if (arr[center] < data) {
      head = center + 1;
    }
    if (arr[center] > data) {
      tail = center - 1;
    }
  }
  return "見つかりませんでした";
}

console.log(binarySearch(array)); // 5番目の要素が一致

単純選択法（選択ソート）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const array = [5, 3, 8, 6, 9, 2]; // ソートする配列

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i; // arr[i]を暫定最小値とする

    for (let k = i + 1; k < arr.length; k++) {
      if (arr[k] < arr[indexMin]) {
        indexMin = k;
      }
    }
    // 最小値とarr[i]の値を交換する    
    [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]];
  }
  return arr;
}

console.log(selectionSort(array)); // [2, 3, 5, 6, 8, 9]

単純交換法（バブルソート）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const array = [5, 3, 8, 6, 9, 2]; // ソートする配列

function bubbleSort(arr) {
  for (let k = 0; k < arr.length - 1; k++) {

    for (let i = arr.length - 1; i > k; i--) {
      if (arr[i - 1] > arr[i]) {
        // 隣り合った要素の値を交換する 
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
      }
    }
  }
  return arr;
}

console.log(bubbleSort(array)); // [2, 3, 5, 6, 8, 9]

単純挿入法（挿入ソート）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const array = [5, 3, 8, 6, 9, 2]; // ソートする配列

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {

    let x = arr[i]; // 挿入したいデータを変数xに保存する
    let k = i; // 空き要素のインデックスを変数kに保存する

    while (k > 0 && arr[k - 1] > x) {
      arr[k] = arr[k - 1];
      k--;
    }
    arr[k] = x;
  }
  return arr;
}

console.log(insertionSort(array)); // [2, 3, 5, 6, 8, 9]

クイックソート

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
32
33
const array = [5, 3, 8, 6, 9, 2]; // ソートする配列

function quickSort(arr, left, right) {
  // 基準値は一番左の要素arr[left]とする
  let i = left + 1; // 基準値より大きい要素を探すための変数i
  let k = right; // 基準値より小さい要素を探すための変数k
  
  while (true) {
    while (arr[i] < arr[left]) i++;
    while (arr[k] > arr[left]) k--; 

    if (i >= k) break;
    // 大きいデータと小さいデータを交換する
    [arr[i], arr[k]] = [arr[k], arr[i]];
    
    i++;
    k--;
  }
  // 基準値を大小データの真ん中に移動する
  if (arr[left] > arr[k]) {
    [arr[left], arr[k]] = [arr[k], arr[left]];
  }
  // 再帰的に処理を繰り返す
  if (left < k - 1) {
    quickSort(arr, left, k - 1);
  }
  if (k + 1 < right) {
    quickSort(arr, k + 1, right);
  }
}

quickSort(array, 0, array.length - 1);
console.log(array); // [2, 3, 5, 6, 8, 9]

エラトステネスのふるい

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
function eratosthenes(num) {
  // 指定された数までのインデックスをもつ配列を作りすべての要素に1を代入する
  const arr = [];
  for (let i = 0; i <= num; i++) {
    arr.push(1);
  }
  // 2より大きい素数の倍数に0を代入する
  let k = 2;
  while(k * k <= num) {
    let i = k;
    while (i <= num / k) {
      arr[k * i] = 0;
      i++;
    }
    k++;
  }
  // 0と1以外の1が代入された要素のインデックスを取り出す
  const result = [];
  for (let j = 2; j < arr.length; j++) {
    if(arr[j] === 1) {
      result.push(j);
    }
  }
  return result;
}

console.log(eratosthenes(10)); // [2, 3, 5, 7]
console.log(eratosthenes(100)); 
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

ユークリッドの互除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function euclid(num1, num2) {
  let a, b, r;
  // 小さいほうをb、大きいほうをaに入れる
  if(num1 < num2) {
    a = num2;
    b = num1;
  } else {
    a = num1;
    b = num2;
  }
  // 余りが0になるまで割る
  while (a % b !== 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return b;
}

console.log(euclid(221, 143)); // 13

短期のスクールがとりあえず終わりました。ほとんど理解は追いついていたので良かったのですが、授業形態があんまり自分に合わなかったので結構疲れました。簡単だけど課題が出て、とにかくこういうものを作ってみましょうというのに取り組めたのが良かったかな。

それから、このブログのデザインをちょっと変えました。初めにうまく実装できなかったページネーションも実装できているはず…。Googleフォントがきれいに出ないのが残念だなぁ。今使っているPCがかなり低スペックなので、新しいのを注文しているんですけど、ちょっともたついててなかなか届かず。おそらく今週末に届くのでそれからまた次へ進もうかなと思います。