新・明解Javaで学ぶアルゴリズムとデータ構造
演習6-15の解答
| 〔方針１〕に基づいて演習6-14のメソッドquickSort （再帰版・非再帰版）を書きかえよ。
|
// 演習6-15
// クイックソート（任意に抽出した３要素の中央値を枢軸とする：再帰版）
import java.util.Scanner;
class QuickSortEx3A {
//--- a, b, cの中央値を求めて返却 ---//
static int med3(int a, int b, int c) {
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
//--- 配列の要素a[idx1]とa[idx2]を交換 ---//
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
//--- 単純挿入ソート ---//
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 = med3(a[pl], a[(pl + pr)/2], a[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-15
// クイックソート（任意に抽出した３要素の中央値を枢軸とする：非再帰版）
import java.util.Scanner;
class QuickSortEx3B {
//--- a, b, cの中央値を求めて返却 ---//
static int med3(int a, int b, int c) {
if (a >= b)
if (b >= c)
return b;
else if (a <= c)
return a;
else
return c;
else if (a > c)
return a;
else if (b > c)
return c;
else
return b;
}
//--- 配列の要素a[idx1]とa[idx2]を交換 ---//
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
//--- 単純挿入ソート ---//
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 = med3(a[pl], a[(pl + pr)/2], a[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]);
}
}
