📖

クイックソートの実装

2025/01/14に公開

クイックソートの実装

基本情報試験科目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