📖
クイックソートの実装
クイックソートの実装
基本情報試験科目B対策&javaの学習目的でクイックソートをjavaで実装する。
コード全体
import java.util.*;
public class quicksort2 {
public static void QuickSort(int[] a, int left, int right){
int leftPointer = left; //左位置
int rightPointer = right; //右位置
int pivot = a[(leftPointer + rightPointer) / 2]; //分割の軸(配列の中央)
//
do {
while (a[leftPointer] < pivot) leftPointer++; //左位置の要素が分割位置より小さい時、左位置を進める
while (a[rightPointer] > pivot) rightPointer--; //右位置の要素が分割位置より大きい時、右位置を進める
if (leftPointer <= rightPointer){ //左右位置が交差してない場合、交換
int temp = a[leftPointer];
a[leftPointer] = a[rightPointer];
a[rightPointer] = temp;
leftPointer++;
rightPointer--;
}
}while (leftPointer <= rightPointer); //交差するまで
if (left < rightPointer) QuickSort(a, left, rightPointer); //右位置が末尾にくるまで再帰
if (leftPointer < right) QuickSort(a, leftPointer, right);
}
public static void main(String[] args) {
//int [] ary = {2,4,1,3,5,7};
int[] ary = {12, 13, 11, 1, 2, 16, 5, 15, 8, 7, 3, 9, 4, 6, 10, 14};
QuickSort(ary, 0, ary.length - 1);
System.out.println(Arrays.toString(ary));
}
}
クイックソートとは
- 基準となる要素(このソースでは配列の中央)を決め、その要素より小さい要素と大きい要素に分ける
- 最終的に要素数が1になるまで(=左半分の場合、右位置が左端に来るまで)再帰的に繰り返す
参考文献
【Java アルゴリズム修行⑭】クイックソート #Java11 - Qiita
【アルゴリズムたいそう】クイックソートを解説しながら歌ってみた - youtube
Discussion