【Java】クイックソート

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

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

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

クイックソート

package chap06;

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 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);
		}
	}
	
	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]);
		}
	}
}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

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