情報処理技法（Javaプログラミング）II 第12回

ソート（2）

テキストpp.198--213を参照。

課題12

クイックソートに似たアルゴリズムに、クイックセレクトがあります。 これは、配列の中央値、より一般的には k 番目に小さい値を求めるものです。 ここで、単純化のため、

• k 番目は0から始めることとする。 配列 a がソート済みなら、 k 番目に小さい値は a [ k ]となる。
• 配列の要素数は奇数とする。 配列 a の中央値は、 k ＝( a .length－1)／2番目に小さい値となる。

とします。

クイックセレクトでは、配列 a 全体をクイックソートせず、 a [ k ]を含む範囲のみクイックソートすることで、効率的に、 k 番目に小さい値が a [ k ]に来るようにします。

p.203のList 6-9を参考にして、配列の中央値を求めるプログラムを作成してください。 メソッド quickSort の先頭で、 k ＝( a .length－1)／2が left より小さいか right より大きいなら、return文でメソッドを終了すればよいです。

import java.util.Scanner;


class QuickSort4 {
    static void swap(int[] a, int idx1, int idx2) {
        
        
    }
    static void quickSort(int[] a, int left, int right) {
        
        
    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        
    }
}

PS ...\Desktop\java2>  & ... 'QuickSort4'
クイックセレクト（中央値）
要素数：9
x[0]：5
x[1]：8
x[2]：4
x[3]：2
x[4]：6
x[5]：1
x[6]：3
x[7]：9
x[8]：7
中央値は5です。
x[0]＝1
x[1]＝3
x[2]＝2
x[3]＝4
x[4]＝5
x[5]＝6
x[6]＝8
x[7]＝9
x[8]＝7
PS ...\Desktop\java2>

余力のある人は、 k 番目に小さい値を求めるプログラムを作成してください。 メソッド quickSort の先頭で、 k が left より小さいか right より大きいなら、return文でメソッドを終了すればよいです。

import java.util.Scanner;


class QuickSort5 {
    static void swap(int[] a, int idx1, int idx2) {
        
        
    }
    static void quickSort(int[] a, int left, int right, int k) {
        
        
    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        
    }
}

PS ...\Desktop\java2>  & ... 'QuickSort5'
クイックセレクト（k番目に小さい値）
要素数：9
x[0]：5
x[1]：8
x[2]：4
x[3]：2
x[4]：6
x[5]：1
x[6]：3
x[7]：9
x[8]：7
何番目に小さい値を探しますか：5
5番目に小さい値は6です。
x[0]＝5
x[1]＝3
x[2]＝4
x[3]＝2
x[4]＝1
x[5]＝6
x[6]＝7
x[7]＝9
x[8]＝8
PS ...\Desktop\java2>

完成したら、答案（Javaプログラム）をメールで提出してください。 差出人は大学発行のメール・アドレス（学生番号@cis.twcu.ac.jp）とし、宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（12月12日）を明記してください。

参考文献

• 柴田望洋『新・明解Javaで学ぶアルゴリズムとデータ構造 第2版』SBクリエイティブ、2020