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

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

import java.util.Scanner;

public class Main {

    static void insertionSort(int[] a, int n, int h) {
        int numOfMove = 0;

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

            // 変数 j を用意する

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

                // j を h だけ減らす

                numOfMove++;
            }

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

        System.out.println(numOfMove);
    }

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        int[] h = new int[k];
        for (int i = 0; i < k; i++) {
            h[i] = sc.nextInt();
        }

        shellSort(a, n, h, k);
    }
}

import java.util.Scanner;

public class Main {

    static void insertionSort(int a[], int n, int h) {
        int numOfMove = 0;

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

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

            a[j] = x;
        }

        System.out.println(numOfMove);
    }

    static void shellSort(int a[], int n, int[] h, int k) {
        for (int i = 0; i < k; i++) {
            insertionSort(a, n, h[i]);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int k = sc.nextInt();

        int h[] = new int[k];
        for (int i = 0; i < k; i++) {
            h[i] = sc.nextInt();
        }

        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

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

期待する出力値

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

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

「シェルソート」の問題を見る

入力される値

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 が半角スペース区切りで与えられます。

有料プランで現役エンジニアに相談可能！

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

実行する

採点する

入力
出力
コンパイルエラー
実行時エラー

出力タイプ：

コード判定結果

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

入力される値

期待する出力値

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

入力される値

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