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

戻る  

演習6-11の解答

// 演習6-11
// クイックソート（配列と要素数を受け取るメソッドを多重定義）

import java.util.Scanner;

class QuickSortOverload {

   //--- 配列の要素a[idx1]とa[idx2]を交換 ---//
   static void swap(int[] a, int idx1, int idx2) {
      int t = a[idx1];  a[idx1] = a[idx2];  a[idx2] = t;
   }

   //--- クイックソート（left, right … 先頭＆末尾要素のインデックス）---//
   static void quickSort(int[] a, int left, int right) {
      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 (left < pr)  quickSort(a, left, pr);
      if (pl < right) quickSort(a, pl, right);
   }

   //--- クイックソート（n … 要素数）---//
   static void quickSort(int[] a, int n) {
      quickSort(a, 0, n - 1);
   }

   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, nx);               // 配列xをクイックソート

      System.out.println("昇順にソートしました。");
      for (int i = 0; i < nx; i++)
         System.out.println("x[" + i + "]＝" + x[i]);
   }
}

戻る