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

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;

        // 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);
    }
}

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 でシェルソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

入力される値

4
8 1 3 2
1
1

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

期待する出力値

Tips

動画へ戻る

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

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

詳しい説明を読む

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

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

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

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

入力される値

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編5: 効率的なソートアルゴリズム > シェルソートの実装

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

コードの実行

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

出力タイプ：