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

戻る  

演習6-14の解答

// 演習6-14
// クイックソート（要素数が9以下であれば単純挿入ソートに切りかえ：再帰版）

import java.util.Scanner;

class QuickSortEx2A {

   //--- 配列の要素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 = a[(pl + pr) / 2];   // 枢軸（中央の要素）

         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-14
// クイックソート（要素数が9以下であれば単純挿入ソートに切りかえ：非再帰版）

import java.util.Scanner;

class QuickSortEx2B {

   //--- 配列の要素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 = a[(left + right) / 2];      // 枢軸は中央の要素
            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]);
   }
}

戻る