新・アルゴリズムとデータ構造入門 JavaScript編5:シェルソートの実装

const insertionSort = (a, n, h) => {
  var numOfMove = 0;

  // i が h から n - 1 までのループを書く
  for (var i = /* */; i < /* */; i++) {
    // A_i を x に保存する

    // 変数 j を用意する

    // j が 0 以上で、A_j が x より大きい間
    while (/* */) {
      // A_j を h だけ右にずらす

      // j を h だけ減らす

      numOfMove++;
    }

    // A_{j+h} に x を代入する
  }

  console.log(numOfMove);
};

const shellSort = (a, n, h, k) => {
  for (var i = 0; i < k; i++) {
    // 間隔 h の挿入ソートを呼び出す
    insertionSort(a, n, /* */);
  }
};

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim().split("\n");

const n = Number(input[0]);
const a = input[1].split(" ").map(x => Number(x));
const k = Number(input[2]);
const h = input[3].split(" ").map(x => Number(x));

shellSort(a, n, h, k);

const insertionSort = (a, n, h) => {
  var numOfMove = 0;

  // i が h から n - 1 までのループを書く
  for (var i = /* */; i < /* */; i++) {
    // A_i を x に保存する

    // 変数 j を用意する

    // j が 0 以上で、A_j が x より大きい間
    while (/* */) {
      // A_j を h だけ右にずらす

      // j を h だけ減らす

      numOfMove++;
    }

    // A_{j+h} に x を代入する
  }

  console.log(numOfMove);
};

const shellSort = (a, n, h, k) => {
  for (var i = 0; i < k; i++) {
    // 間隔 h の挿入ソートを呼び出す
    insertionSort(a, n, /* */);
  }
};

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim().split("\n");

const n = Number(input[0]);
const a = input[1].split(" ").map(x => Number(x));
const k = Number(input[2]);
const h = input[3].split(" ").map(x => Number(x));

shellSort(a, n, h, k);

const insertionSort = (a, n, h) => {
  var numOfMove = 0;

  for (var i = h; i < n; i++) {
    var x = a[i];
    var j = i-h;

    while (j >= 0 && a[j] > x) {
      a[j+h] = a[j];
      j -= h;
      numOfMove++;
    }

    a[j] = x;
  }

  console.log(numOfMove);
};

const shellSort = (a, n, h, k) => {
  for (var i = 0; i < k; i++) {
    // 間隔 h の挿入ソートを呼び出す
    insertionSort(a, n, h[i]);
  }
};

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim().split("\n");

const n = Number(input[0]);
const a = input[1].split(" ").map(x => Number(x));
const k = Number(input[2]);
const h = input[3].split(" ").map(x => Number(x));

shellSort(a, n, h, k);

const insertionSort = (a, n, h) => {
  var numOfMove = 0;

  for (var i = h; i < n; i++) {
    var x = a[i];
    var j = i-h;

    while (j >= 0 && a[j] > x) {
      a[j+h] = a[j];
      j -= h;
      numOfMove++;
    }

    a[j] = x;
  }

  console.log(numOfMove);
};

const shellSort = (a, n, h, k) => {
  for (var i = 0; i < k; i++) {
    // 間隔 h の挿入ソートを呼び出す
    insertionSort(a, n, h[i]);
  }
};

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim().split("\n");

const n = Number(input[0]);
const a = input[1].split(" ").map(x => Number(x));
const k = Number(input[2]);
const h = input[3].split(" ").map(x => Number(x));

shellSort(a, n, h, k);

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「正しくシェルソートを実装する」

整数 n と要素数 n の数列 A 、整数 k と要素数 k の数列 h が与えられるので、この数列を与えられた間隔列 h でシェルソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

【制約】
・入力は全て整数
・ 1 ≦ k < n ≦ 10
・ 1 ≦ (数列 A の各要素) ≦ 100
・ 1 = h*k < h*{k+1} < ... < h_1 ≦ 100

入力される値

4
8 1 3 2
1
1

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃03:シェルソートの実装

実際にシェルソートを実装してみます。そして、効率的にソートが行われていることを確認してみましょう。

「シェルソート」へのリンク

https://paiza.jp/works/mondai/sort_efficient/sort_efficient__shell

入力される値

n
A_1 A_2 ... A_n
k
h_1 h_2 ... h_k

・入力はすべて整数
・ 1行目に、数列の要素数 n が与えられます。
・ 2行目に、数列の要素 A_1, A_2, ... , A_n が半角スペース区切りで与えられます。
・ 3行目に、間隔列の要素数 k が与えられます。
・ 2行目に、間隔列の要素 h_1, h_2, ... , h_k が半角スペース区切りで与えられます。

プログラミング学習 > JavaScript > 新・アルゴリズムとデータ構造入門 JavaScript編 > 新・アルゴリズムとデータ構造入門 JavaScript編5: 効率的なソートアルゴリズム > シェルソートの実装

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：