新・明解Javaで学ぶアルゴリズムとデータ構造
演習6-16の解答
| 〔方針２〕に基づいて演習6-14のメソッドquickSort （再帰版・非再帰版）を書きかえよ。
|
// 演習6-16
// クイックソート（先頭／中央／末尾要素をソートして中央値を枢軸とする：再帰版）
import java.util.Scanner;
class QuickSortEx4A {
//--- 配列の要素a[idx1]とa[idx2]を交換 ---//
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
//--- x[a], x[b], x[c]をソート（中央値のインデックスを返却）---//
static int sort3Elem(int[] x, int a, int b, int c) {
if (x[b] < x[a]) swap(x, b, a);
if (x[c] < x[b]) swap(x, c, b);
if (x[b] < x[a]) swap(x, b, a);
return b;
}
//--- 単純挿入ソート ---//
static void insertionSort(int[] a, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int tmp = a[i];
int j;
for (j = i; j > left && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
//--- 配列を分割する ---//
static void quickSort(int[] a, int left, int right) {
if (right - left < 9)
insertionSort(a, left, right);
else {
int pl = left; // 左カーソル
int pr = right; // 右カーソル
int x; // 枢軸
int m = sort3Elem(a, pl, (pl + pr) / 2, pr);
x = a[m];
swap(a, m, right - 1);
pl++;
pr--;
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
if (pr - left < right - pl) {
int temp;
temp = left; left = pl; pl = temp;
temp = right; right = pr; pr = temp;
}
if (left < pr) quickSort(a, left, pr);
if (pl < right) quickSort(a, pl, right);
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("クイックソート");
System.out.print("要素数：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
quickSort(x, 0, nx - 1); // 配列xをクイックソート
System.out.println("昇順にソートしました。");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "]＝" + x[i]);
}
}
// 演習6-16
// クイックソート（先頭／中央／末尾要素をソートして中央値を枢軸とする：非再帰版）
import java.util.Scanner;
class QuickSortEx4B {
//--- 配列の要素a[idx1]とa[idx2]を交換 ---//
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
//--- x[a], x[b], x[c]をソート（中央値のインデックスを返却）---//
static int sort3Elem(int[] x, int a, int b, int c) {
if (x[b] < x[a]) swap(x, b, a);
if (x[c] < x[b]) swap(x, c, b);
if (x[b] < x[a]) swap(x, b, a);
return b;
}
//--- 単純挿入ソート ---//
static void insertionSort(int[] a, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int tmp = a[i];
int j;
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
//--- クイックソート（非再帰版）---//
static void quickSort(int[] a, int left, int right) {
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left);
rstack.push(right);
while (lstack.isEmpty() != true) {
int pl = left = lstack.pop(); // 左カーソル
int pr = right = rstack.pop(); // 右カーソル
if (right - left < 9)
insertionSort(a, left, right);
else {
int x; // 枢軸
int m = sort3Elem(a, pl, (pl + pr) / 2, pr);
x = a[m];
swap(a, m, right - 1);
pl++;
pr--;
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
if (pr - left < right - pl) {
int temp;
temp = left; left = pl; pl = temp;
temp = right; right = pr; pr = temp;
}
if (left < pr) {
lstack.push(left);
rstack.push(pr);
}
if (pl < right) {
lstack.push(pl);
rstack.push(right);
}
}
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("クイックソート");
System.out.print("要素数：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
quickSort(x, 0, nx - 1); // 配列xをクイックソート
System.out.println("昇順にソートしました。");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}
