BohYoh.comトップページへ

Javaによるアルゴリズムとデータ構造

戻る  

演習6-13の解答

 プッシュ・ポップ・分割の様子を詳細に表示するようにList 6-10のプログラムを書きかえよ。

// 演習6-13 // クイックソート(非再帰版:スタックへのプッシュ・ポップの様子を表示) import java.util.Scanner; class QuickSort2Ex {     //--- 配列の要素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) {         IntStack lstack = new IntStack(right-left+1);         IntStack rstack = new IntStack(right-left+1);         lstack.push(left);         rstack.push(right);         System.out.printf("a[%d]~a[%d]を分割する問題をスタックにプッシュします。\n", left, right);         System.out.print("Lstack:"); lstack.dump();         System.out.print("Rstack:"); rstack.dump();         while (lstack.isEmpty() != true) {             int    pl = left  = lstack.pop();        // 左カーソル             int    pr = right = rstack.pop();        // 右カーソル             int    x = a[(left + right2];        // 枢軸は中央の要素             System.out.printf("スタックから分割する問題を取り出しました。a[%d]~a[%d]を分割します。\n", left, right);             do {                 while (a[pl< xpl++;                 while (a[pr> xpr--;                 if (pl <= pr)                     swap(a, pl++, pr--);             while (pl <= pr);             if (left < pr) {                 lstack.push(left);            // 先頭側グループの範囲                 rstack.push(pr);            // (インデックス)をプッシュ                 System.out.printf("a[%d]~a[%d]を分割する問題をスタックにプッシュします。\n", left, pr);                 System.out.print("Lstack:"); lstack.dump();                 System.out.print("Rstack:"); rstack.dump();             }             if (pl < right) {                 lstack.push(pl);            // 末尾側グループの範囲                 rstack.push(right);            // (インデックス)をプッシュ                 System.out.printf("a[%d]~a[%d]を分割する問題をスタックにプッシュします。\n", pl, right);                 System.out.print("Lstack:"); lstack.dump();                 System.out.print("Rstack:"); rstack.dump();             }         }     }     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]);     } }


戻る