EvbCFfp1XB

problem and my answer.

April 2012

問題を解いてみました。

import java.util.Arrays;

public class Chapter8ElementarySortingMethods {
public static void main(String[] args) {
// problem1();
// problem2();
// problem3();
// problem4();
// problem5();
// problem6();
// problem7();
// problem8();
// problem9();
problem10();
}

/**
* 1. 4つのレコードを整列するための”比較と交換”命令の列を示せ.
*/
static void problem1() {
int[] a = new int[4];
for (int i = 0; i < a.length; i++) {
a[i] = (int) (100 * Math.random());
}
sort4(a);
print(a);
}

private static void sort4(int[] a) {
if (a[0] > a[1]) {
swap(a, 0, 1);
}
if (a[0] > a[2]) {
swap(a, 0, 2);
}
if (a[0] > a[3]) {
swap(a, 0, 3);
}
if (a[1] > a[2]) {
swap(a, 1, 2);
}
if (a[1] > a[3]) {
swap(a, 1, 3);
}
if (a[2] > a[3]) {
swap(a, 2, 3);
}
}

private static void swap(int[] a, int i, int j) {
int s = a[i];
a[i] = a[j];
a[j] = s;
}

/**
* 2. すでに整列しているファイルに対して、3つの初等的な整列法(選択整列方、挿入整列方、バブル整列方)の中で最も早いのはどれか?
*/
static void problem2() {
int[] a = new int[10000];
for (int i = 0; i < a.length; i++) {
a[i] = i;
}

long start = System.nanoTime();
selection(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

start = System.nanoTime();
insertion(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

start = System.nanoTime();
bubble(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static void bubble(int[] a) {
for (int i = a.length - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
}
}
}
}

private static void insertion(int[] a) {
for (int i = 1; i < a.length; i++) {
int v = a[i];
int j = i;
for (; j - 1 >= 0 && a[j - 1] > v; j--) {
a[j] = a[j - 1];
}
a[j] = v;
}
}

private static void selection(int[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
swap(a, min, i);
}
}

/**
* 3. 逆順に並んでいるファイルに対して、3つの初等的な整列法(選択整列方、挿入整列方、バブル整列方)の中で最も早いのはどれか?
*/
static void problem3() {
int[] a = new int[10000];

for (int i = 0; i < a.length; i++) {
a[i] = a.length - i;
}
long start = System.nanoTime();
selection(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

for (int i = 0; i < a.length; i++) {
a[i] = a.length - i;
}
start = System.nanoTime();
insertion(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

for (int i = 0; i < a.length; i++) {
a[i] = a.length - i;
}
start = System.nanoTime();
bubble(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

/**
* 4. 次の命題が正しいかどうか調べよ.”整数の整列のためには3つの初等的な整列法の中で最も早いのが選択整列法、次が挿入整列法、
* その後がバブル整列法である.”
*/
static void problem4() {
int[] a = new int[10000];
random(a);
int[] b = Arrays.copyOf(a, a.length);
int[] c = Arrays.copyOf(a, a.length);

long start = System.nanoTime();
selection(a);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

start = System.nanoTime();
insertion(b);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

start = System.nanoTime();
bubble(c);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

/**
* 5. 挿入整列法に番兵を使うと必ずしもうまくない場合があるか?(シェルソートで現れたものがその一例であるが、それ以外にあるか?)
*/
static void problem5() {
}

/**
* 6. シェルソートによって、EASYQUESTIONを7-整列して、次に3-整列すると、何回比較するか?
*/
static void problem6() {
String s = "EASYQUESTION";
int[] a = new int[s.length()];
for (int i = 0; i < a.length; i++) {
a[i] = s.charAt(i);
}
System.out.format("%d\n", shellsortcount(a, new int[] { 3, 7, }));
printchar(a);
}

/**
* 7. シェルソートの増分列として、8,4,2,1がうまくないような入力例を示せ.
*/
static void problem7() {
int[] a = new int[100000];
random(a);
int[] b = Arrays.copyOf(a, a.length);

int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
h[i] = 2 * h[i - 1];
if (h[i] > a.length) {
h = Arrays.copyOf(h, i);
break;
}
}
long start = System.nanoTime();
shellsort(a, h);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);

int[] h2 = new int[100];
h2[0] = 1;
for (int i = 1; i < h2.length; i++) {
h2[i] = 3 * h2[i - 1] + 1;
if (h2[i] > a.length / 9) {
h2 = Arrays.copyOf(h2, i);
break;
}
}
start = System.nanoTime();
shellsort(b, h2);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static void print(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.format("%d,", a[i]);
}
System.out.println();
}

private static int shellsortcount(int[] a, int[] h) {
int count = 0;
for (int hi = h.length - 1; hi >= 0; hi--) {
int b = h[hi];
for (int i = b; i < a.length; i++) {
int v = a[i];
int j = i;
for (; j - b >= 0 && count++ >= 0 && a[j - b] > v; j -= b) {
a[j] = a[j - b];
}
a[j] = v;
}
}
return count;
}

private static void shellsort(int[] a, int[] h) {
for (int k = h.length - 1; k >= 0; k--) {
int b = h[k];
for (int i = b; i < a.length; i++) {
int v = a[i];
int j;
for (j = i; j - b >= 0 && a[j - b] > v; j -= b) {
a[j] = a[j - b];
}
a[j] = v;
}
}
}

private static void printchar(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.format("%c", a[i]);
}
System.out.println();
}

/**
* 8. 選択整列法は安定か?挿入整列法とバブル整列法はどうか?
*/
static void problem8() {
{
A[] a = new A[3];
for (int i = 0; i < a.length; i++) {
a[i] = new A();
a[i].c = i;
}
a[0].b = 1;
a[1].b = 1;
a[2].b = 0;
printA(a);
selection(a);
printA(a);
}
{
A[] a = new A[10000];
for (int i = 0; i < a.length; i++) {
a[i] = new A();
a[i].b = (int) (100 * Math.random());
a[i].c = i;
}
insertion(a);
for (int i = 1; i < a.length; i++) {
if (a[i].b == a[i - 1].b) {
if (a[i].c < a[i - 1].c) {
System.out.println("not stable");
break;
}
}
}
}
{
A[] a = new A[10000];
for (int i = 0; i < a.length; i++) {
a[i] = new A();
a[i].b = (int) (100 * Math.random());
a[i].c = i;
}
bubble(a);
for (int i = 1; i < a.length; i++) {
if (a[i].b == a[i - 1].b) {
if (a[i].c < a[i - 1].c) {
System.out.println("not stable");
break;
}
}
}
}
}

private static void printA(A[] a) {
for (int i = 0; i < a.length; i++) {
System.out.format("(%d,%d)", a[i].b, a[i].c);
}
System.out.println();
}

static class A {
int b;
int c;
}

private static void bubble(A[] a) {
for (int i = a.length - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
if (a[j - 1].b > a[j].b) {
swap(a, j - 1, j);
}
}
}
}

private static void swap(A[] a, int i, int j) {
A aa = a[i];
a[i] = a[j];
a[j] = aa;
}

private static void insertion(A[] a) {
for (int i = 1; i < a.length; i++) {
A v = a[i];
int j = i;
for (; j - 1 >= 0 && a[j - 1].b > v.b; j--) {
a[j] = a[j - 1];
}
a[j] = v;
}
}

private static void selection(A[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j].b < a[min].b) {
min = j;
}
}
swap(a, min, i);
}
}

/**
* 9. 要素がわずか2種類(xかyのいずれか)しかないファイルを整列するための分配計数法の変形版を考えよ.
*/
static void problem9() {
int[] a = new int[10];
for (int i = 0; i < a.length; i++) {
a[i] = Math.random() > 0.5 ? 'x' : 'y';
}
printchar(a);

int[] count = new int[2];
for (int i = 0; i < a.length; i++) {
count[a[i] - 'x']++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
int[] b = new int[a.length];
for (int i = a.length - 1; i >= 0; i--) {
b[--count[a[i] - 'x']] = a[i];
}
System.arraycopy(b, 0, a, 0, b.length);
printchar(a);
}

/**
* 10.
* 実験によって、シェルソートの増分列をいろいろ試してみよ.1000個の要素のランダムなファイルに対して、本文の増分列よりもっと早いものを見つけよ.
*/
static void problem10() {
h1();
h2();
h3();
h4();
h5();
h6();
h7();
h8();
h9();
h10();
prime();
h11();
h12();
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h1() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
for (int i = 0; i < h.length; i++) {
h[i] = (int) (a.length / (Math.pow(2, i)));
if (h[i] <= 0) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h2() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
for (int i = 0; i < h.length; i++) {
h[i] = 2 * (int) (a.length / (Math.pow(2, i + 1))) + 1;
if (h[i] <= 1) {
h = Arrays.copyOf(h, i + 1);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h3() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
for (int i = 0; i < h.length; i++) {
h[i] = (int) (Math.pow(2, i + 1) - 1);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h4() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
h[i] = (int) (Math.pow(2, i) + 1);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h5() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
h[i] = 3 * h[i - 1] + 1;
// h[i] = (int) (Math.pow(3, i + 1) - 1) / 2;
// 1 4 13 40 121 364 1093 3280 9841 29524 88573 265720
if (h[i] >= a.length / 9) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h6() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
h[i] = (int) (Math.pow(4, i) + 3 * Math.pow(2, i - 1) + 1);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h7() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
int index = 0;
for (int i = 1; i < h.length; i++) {
h[index++] = (int) (9 * (Math.pow(4, i - 1) - Math.pow(2, i - 1)) + 1);
h[index++] = (int) ((Math.pow(4, i + 1) - 6 * Math.pow(2, i)) + 1);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h8() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = n;
for (int i = 1; i < h.length; i++) {
h[i] = Math.max((5 * h[i - 1]) / 11, 1);
if (h[i] <= 1) {
h = Arrays.copyOf(h, i + 1);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h9() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
double e = 1;
for (int i = 1; i < h.length; i++) {
e = 2.25 * e + 1;
h[i] = (int) Math.ceil(e);
}
print(h);
// 1 4 9 20 46 103 233 525 1182 2660 5985 13467 30301 68178 153401
// 345152 776591
for (int i = 0; i < h.length; i++) {
h[i] = (int) (Math.ceil((Math.pow(9, i + 1) - Math.pow(4, i + 1))
/ (5 * Math.pow(4, i))));
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

/** http://en.wikipedia.org/wiki/Shellsort */
private static void h10() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
h[1] = 4;
h[2] = 10;
h[3] = 23;
h[4] = 57;
h[5] = 132;
h[6] = 301;
h[7] = 701;
for (int i = 8; i < h.length; i++) {
h[i] = (int) Math.floor(2.25 * h[i - 1]);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

static boolean[] isprime;

private static void prime() {
int n = 1000000;

sieve(n);

int[] a = new int[n];

double d = 2.24;
{
int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
for (int j = (int) Math.ceil(d * h[i - 1]); j < isprime.length; j++) {
if (isprime[j]) {
h[i] = j;
break;
}
}
if (d * h[i] >= a.length) {
h = Arrays.copyOf(h, i);
break;
}
}
print(h);

printTime(a, h);
}
}

private static void h11() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = 1;
for (int i = 1; i < h.length; i++) {
h[i] = (int) Math.ceil(2.36291 * h[i - 1]);
if (h[i] >= a.length) {
h = Arrays.copyOf(h, i - 1);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

private static void h12() {
int n = 1000000;

int[] a = new int[n];

int[] h = new int[100];
h[0] = (int) (n / 2.2 - 1);
for (int i = 1; i < h.length; i++) {
h[i] = (int) (h[i - 1] / 2.2) - 1;
if (h[i] <= 1) {
h[i] = 1;
h = Arrays.copyOf(h, i + 1);
Arrays.sort(h);
break;
}
}
print(h);

printTime(a, h);
}

private static void printTime(int[] a, int[] h) {
for (int k = 0; k < 10; k++) {
random(a);
int count = 0;
long start = System.nanoTime();
// shellsort(a, h);
count = shellsortcount(a, h);
System.out.format("%d, %f\n", count,
(System.nanoTime() - start) / 1e9);
}
}

private static void random(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = (int) (a.length * Math.random());
}
}

private static void sieve(int n) {
isprime = new boolean[n + 1];
isprime[2] = true;
for (int i = 3; i <= n; i += 2) {
isprime[i] = true;
}
int L = (int) Math.sqrt(n);
for (int i = 3; i <= L; i += 2) {
if (isprime[i]) {
int j2 = n / i;
for (int j = j2 % 2 == 1 ? j2 : j2 - 1; j >= i; j -= 2) {
if (isprime[j]) {
isprime[i * j] = false;
}
}
}
}
}
}

このページのトップヘ