EvbCFfp1XB

problem and my answer.

/**
* Chapter 10. Radix Sorting - Problem4 - Robert Sedgewick Algorithms in C++<br>
* 真か偽か - 直接基数法の実行時間は、入力ファイルでキーが並ぶ順序に依存しない。その理由も説明せよ。
*/
public class Chapter10RadixSortingProblem4 {
public static void main(String[] args) {
System.out
.println("radixLeastSignificantDigitのコードはキーが並ぶ順序に依存しないため真です。");
int[] a = new int[1000000];
System.out.println("ascending order");
for (int j = 0; j < a.length; j++) {
a[j] = j;
}
for (int i = 0; i < 10; i++) {
run(a);
}
System.out.println("descending order");
for (int i = 0; i < 10; i++) {
for (int j = 0; j < a.length; j++) {
a[j] = (a.length - 1) - j;
}
run(a);
}
System.out.println("random");
for (int i = 0; i < 10; i++) {
for (int j = 0; j < a.length; j++) {
swap(a, j, (int) (a.length * Math.random()));
}
run(a);
}
}

private static void run(int[] a) {
long start = System.nanoTime();
radixLeastSignificantDigit(a, 0, a.length - 1);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
isSorted(a);
}

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

private static int bit(int a, int d, int k) {
return (a >> d) & (~((~0) << k));
}

private static void radixLeastSignificantDigit(int[] a, int l, int r) {
int[] b = new int[a.length];
int m = 8;
int[] count = new int[(1 << m)];
for (int d = 0; d < 32 / m; d++) {
for (int j = 0; j < count.length; j++)
count[j] = 0;
for (int i = l; i <= r; i++)
count[bit(a[i], m * d, m)]++;
for (int j = 1; j < count.length; j++)
count[j] += count[j - 1];
for (int i = r; i >= l; i--)
b[--count[bit(a[i], m * d, m)]] = a[i];
for (int i = l; i <= r; i++)
a[i] = b[i];
}
}

private static void isSorted(int[] a) {
for (int i = 1; i < a.length; i++) {
if (a[i - 1] > a[i]) {
System.out.println("unsorted");
break;
}
}
}
}

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 10 Radix Sorting<br>
* Problem3<br>
* 基数交換法を修整して、すべてのキーにおいて等しい先頭のビット列をとばすようにせよ。どのような状況でこの修整が役に立つか?
*/
public class Chapter10RadixSortingProblem3 {
public static void main(String[] args) {
int[] a = new int[1000000];
random(a, 2);
long start = System.nanoTime();
radixexchangesortSkip(a, 0, a.length - 1, 31);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
isSorted(a);
}

private static int bit(int a, int d) {
return bit(a, d, 1);
}

private static int bit(int a, int d, int k) {
return (a >> d) & (~((~0) << k));
}

private static void radixexchangesortSkip(int[] a, int l, int r, int d) {
if (r <= l || d < 0)
return;
if (d > 1) {
int max = d;
for (int i = l + 1; i <= r; i++) {
for (; max > 0
&& bit(a[i], d - max, 31) != bit(a[i - 1], d - max, 31); max--) {
}
}
d -= max;
}
int i = l, j = r;
while (j != i) {
while (bit(a[i], d) == 0 && (i < j))
i++;
while (bit(a[j], d) == 1 && (j > i))
j--;
swap(a, i, j);
}
if (bit(a[r], d) == 0)
j++;
radixexchangesortSkip(a, l, j - 1, d - 1);
radixexchangesortSkip(a, j, r, d - 1);
}

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

private static void isSorted(int[] a) {
for (int i = 1; i < a.length; i++) {
if (a[i - 1] > a[i]) {
System.err.println("unsorted");
break;
}
}
}

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

問題を解いてみました。

/**
* Robert Sedgewick Algorithms in C++<br>
* Chapter 10 Radix Sorting<br>
* Problem2<br>
* 基数交換法で再帰呼び出しを除去することがクイックソートほど重要でないのはなぜか?
*/
public class Chapter10RadixSortingProblem2 {
public static void main(String[] args) {
int[] a = new int[100000];
for (int i = 0; i < a.length; i++) {
a[i] = i;
}

long start = System.nanoTime();
radixexchangesort(a, 0, a.length - 1, 31);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
isSorted(a);

start = System.nanoTime();
try {
quicksortRecursive(a, 0, a.length - 1);
} catch (StackOverflowError e) {
System.out.println("StackOverflowError");
}
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

private static int bit(int i, int d) {
return (i >> d) & 1;
}

private static void radixexchangesort(int[] a, int l, int r, int d) {
int i = l, j = r;
if (r <= l || d < 0)
return;
while (j != i) {
while (bit(a[i], d) == 0 && (i < j))
i++;
while (bit(a[j], d) == 1 && (j > i))
j--;
swap(a, i, j);
}
if (bit(a[r], d) == 0)
j++;
radixexchangesort(a, l, j - 1, d - 1);
radixexchangesort(a, j, r, d - 1);
}

private static void quicksortRecursive(int[] a, int l, int r) {
if (l < r) {
int i = partition(a, l, r);
quicksortRecursive(a, l, i - 1);
quicksortRecursive(a, i + 1, r);
}
}

private static int partition(int[] a, int l, int r) {
int v = a[r];
int i = l - 1;
int j = r;
for (;;) {
for (; a[++i] < v;) {
}
for (; --j >= l && a[j] > v;) {
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, i, r);
return i;
}

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

private static void isSorted(int[] a) {
for (int i = 1; i < a.length; i++) {
if (a[i - 1] > a[i]) {
System.err.println("unsorted");
break;
}
}
}
}

このページのトップヘ