線形検索、バイナリ検索、バブルソート

既存のブログの内容をDevelopgに移行した記事です.

練習問題

1.線形検索

線形検索により、所与の配列(array)の所与の値(target)が要素として存在することを確保し、存在する場合はインデックスを返し、存在しない場合は-1の関数を返す.ただし、構築関数としての関数を使用せずにfor文を使用して実装する必要があります.

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(linearSearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(linearSearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(linearSearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(linearSearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(linearSearch([1, 2, 3, 4, 5, 6], 7)); // -1

2.検索バイナリ

バイナリ検索により、所与の配列(array)の所与の値(target)が要素として存在することを確認し、存在する場合はインデックスを返し、存在しない場合は-1の関数を返す.ただし、次のコンストラクタ関数を除いて、コンストラクタ関数を使用するのではなく、while文を使用して実装する必要があります.

初めて

function binarySearch(array, target) {
  let midIndex = Math.floor(array.length / 2);
  let maxIndex = array.length - 1;
  let minIndex = 0;

  while (maxIndex !== midIndex) {
    if (array[midIndex] > target) {
      maxIndex = --midIndex;
    } else if (array[midIndex] < target) {
      minIndex = ++midIndex;
    } else {
      return midIndex;
    }
    midIndex = Math.floor((maxIndex + minIndex) / 2);
  }

  return array[midIndex] === target ? midIndex : -1;
}

console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

質問:

whileドアが終了しても、検索値は最後またはなしでもう一度

をマスクする必要があります.

変数名はすべてmで始まる、可読性差

whileゲートの最初の行Math.床を使うとwhileドアの中だけMath床

2回目

function binarySearch(array, target) {
  let startIndex = 0;
  let endIndex = array.length - 1;
  let midIndex;

  while (startIndex <= endIndex) {
    midIndex = Math.floor((startIndex + endIndex) / 2);
    if (array[midIndex] < target) {
      startIndex = ++midIndex;
    } else if (array[midIndex] > target) {
      endIndex = --midIndex;
    } else {
      return midIndex;
    }
  }
  return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5, 6], 1)); // 0
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3)); // 2
console.log(binarySearch([1, 2, 3, 4, 5, 6], 5)); // 4
console.log(binarySearch([1, 2, 3, 4, 5, 6], 6)); // 5
console.log(binarySearch([1, 2, 3, 4, 5, 6], -1)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 0)); // -1
console.log(binarySearch([1, 2, 3, 4, 5, 6], 7)); // -1

改善点:

while文条件式改善

変数名

を変更

Math.フロア冗長性向上

3.泡の位置合わせ

与えられたアレイ(array)をソートする関数は、泡ソートによって実現される.ただし、構築関数としての関数を使用せずにfor文を使用して実装する必要があります.

初めて

function bubbleSort(array) {
  let replace;
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1; j++) {
      if (array[j] > array[j + 1]) {
        replace = array[j];
        array[j] = array[j + 1];
        array[j + 1] = replace;
      }
    }
  }
  return array;
}

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]

質問:

whileはドアを回転するたびに、ループ文を書く必要がなく、並べられた最大値の順序で右揃えを行います.

2回目

function bubbleSort(array) {
  let replace;
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        replace = array[j];
        array[j] = array[j + 1];
        array[j + 1] = replace;
      }
    }
  }
  return array;
}

console.log(bubbleSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(bubbleSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(bubbleSort([3, 1, 0, 11, 4, 2, 9, -1])); // [-1, 0, 1, 2, 3, 4]

改善点:

サイクルあたりの最大値をソートするため、-iを追加するとサイクルカウント

が減少する.