新・アルゴリズムとデータ構造入門 Java編4:挿入ソート

import java.util.Scanner;

public class Main {
	static void print(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int[] a, int n) {
		for (int i = 1; i < n; i++) {



			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int[] a, int n) {
		for (int i = 1; i < n; i++) {



			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			// 先に a[i] を保存しておき、x とする
			int x = a[i];
			// 挿入する位置を探すための変数 j を用意する
			int j = i - 1;

			// j が 0 以上かつ a[j] が x より大きい間
			while (j >= 0 && a[j] > x) {
				// a[j] を 1 つ右にずらす

				// j を 1 減らす
				j--;
			}

			// a[j+1] に x を挿入する
			a[j + 1] = x;

			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			// 先に a[i] を保存しておき、x とする
			int x = a[i];
			// 挿入する位置を探すための変数 j を用意する
			int j = i - 1;

			// j が 0 以上かつ a[j] が x より大きい間
			while (j >= 0 && a[j] > x) {
				// a[j] を 1 つ右にずらす

				// j を 1 減らす
				j--;
			}

			// a[j+1] に x を挿入する
			a[j + 1] = x;

			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			int x = a[i];
			int j = i - 1;

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

			a[j + 1] = x;

			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			int x = a[i];
			int j = i - 1;

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

			a[j + 1] = x;

			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			// 先に a[i] を保存しておき、x とする

			// 挿入する位置を探すための変数 j を用意する

			// j が 0 以上かつ a[j] が x より大きい間

			// a[j] を 1 つ右にずらす

			// j を 1 減らす

			// a[j+1] に x を挿入する

			print(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();
		}

		insertionSort(a, n);
	}
}

import java.util.Scanner;

public class Main {
	static void print(int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

	static void insertionSort(int a[], int n) {
		for (int i = 1; i < n; i++) {

			// 先に a[i] を保存しておき、x とする

			// 挿入する位置を探すための変数 j を用意する

			// j が 0 以上かつ a[j] が x より大きい間

			// a[j] を 1 つ右にずらす

			// j を 1 減らす

			// a[j+1] に x を挿入する

			print(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();
		}

		insertionSort(a, n);
	}
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

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

演習課題「挿入ソートの部分的な実装」

整数 n と、要素数 n の整数列 a が与えられるので、挿入ソートで a を小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各 i (i = 1, 2, ..., n - 1) について i 回目の処理が終わった時点での配列を出力してください。

右側のコードエリアには、入力を受け取り、挿入ソートのループ処理と配列の出力をおこなうコードが用意されています。コードを書き加え、問題を解くコードを完成させてください。

入力される値

5
4 1 3 5 2

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

期待する出力値

1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5

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

演習課題「挿入ソート・コード修正」

整数 n と、要素数 n の整数列 a が与えられるので、挿入ソートで a を小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各 i (i = 1, 2, ..., n - 1) について i 回目の処理が終わった時点での配列を出力してください。

右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。

入力される値

5
4 1 3 5 2

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

期待する出力値

1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5

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

演習課題「挿入ソートの実装」

整数 n と、要素数 n の整数列 a が与えられるので、挿入ソートで a を小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各 i (i = 1, 2, ..., n - 1) について i 回目の処理が終わった時点での配列を出力してください。

右側のコードエリアには、入力を受け取るコードが用意されています。コメントを参考にコードを書き加え、問題を解くコードを完成させてください。