【Java】クイックソート

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

基本用語

アルゴリズム

問題を解くためのものであって、明確に定義され、順序付けられた有限個の規則からなる集合。
（「JIS X0001」より。JISとは日本産業規格のこと。）

クイックソート

実装

//--- クイックソート ---//
static void quickSort(int[] a, int left, int right) {
  int point_left  = left;                // 左カーソル
  int point_right = right;               // 右カーソル
  int x  = a[(point_left + point_right) / 2];    // 枢軸（中央の要素）
  
  do {
    while (a[point_left] < x) point_left++;    // ①
    while (a[point_right] > x) point_right--;  // ②
    
    if (point_left <= point_right) {           // ③
      swap(a, point_left++, point_right--);
    }
  } while (point_left <= point_right);         // ④
  
  if (left < point_right) {                    // ⑤
    quickSort(a, left, point_right);
  }
  
  if (point_left < right) {                    // ⑥
    quickSort(a, point_left, right);
  }
}

アルゴリズムイメージ図

利用例

import java.util.Scanner;

public class QuickSort {
	
  //--- 配列の要素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 point_left  = left;                // 左カーソル
    int point_right = right;               // 右カーソル
    int x  = a[(point_left + point_right) / 2];    // 枢軸（中央の要素）
    
    do {
      while (a[point_left] < x) point_left++;    // ①
      while (a[point_right] > x) point_right--;  // ②
      
      if (point_left <= point_right) {           // ③
        swap(a, point_left++, point_right--);
      }
    } while (point_left <= point_right);         // ④
    
    if (left < point_right) {                    // ⑤
      quickSort(a, left, point_right);
    }
    
    if (point_left < right) {                    // ⑥
      quickSort(a, point_left, right);
    }
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    System.out.println("クイックソート");
    System.out.println("要素数：");
    
    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]);
    }
  }
}

実行結果

クイックソート
要素数：5
x[0]：8
x[1]：7
x[2]：6
x[3]：5
x[4]：9
昇順にソートしました。
x[0]=5
x[1]=6
x[2]=7
x[3]=8
x[4]=9

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。