| p.190に示した〔方針１〕に基づいてList 6-9のメソッドquickSort を書きかえよ。 |
// 演習6-11 // クイックソート（抽出した３要素の中央値を枢軸とする） import java.util.Scanner; class QuickSortMed3 { //--- 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 quickSort(int[] a, int left, int right) { int pl = left; // 左カーソル int pr = right; // 右カーソル int x = (pr - pl < 2) ? a[pl] // 枢軸 : 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 (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]); } }
