BohYoh.comトップページへ

新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習6-16の解答

 〔方針2〕に基づいて演習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 + pr2, pr);          x = a[m];          swap(a, m, right - 1);          pl++;          pr--;          do {             while (a[pl< xpl++;             while (a[pr> xpr--;             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 < rightquickSort(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 > && 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 + pr2, pr);             x = a[m];             swap(a, m, right - 1);             pl++;             pr--;             do {                while (a[pl< xpl++;                while (a[pr> xpr--;                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]);    } }


戻る