基本情報技術者の擬似言語の学習のため実際にプログラム化してみました。
基本情報の問題集をもとにフローチャートを作成し、コーディングをおこなっております。
今回は、配列の最初の要素と隣の要素を比較し、大きい方を基準値にしております。
Qiita.java
import java.util.*;
public class QuickSort_2 {
public static void main(String[] args) {
/*
* テストデータ
*
* [3,5,8,4,0,6,9,1,2,7] ok
* [7,7,7,7,7,6,9,1,2,7] ok
* [0,0,0,0,0,0,0,0,0,0] ok
* [80,70,60,50,40,30,20,10] ok
* [70,60,40,70,30,70,50,70] ok
* [80,60,40,70,30,10,50,20] ok
* [80,60,40,70,30,10,50,20] ok
* [80,60,40,70,30,10,50,70] ok
*
*/
try {
Scanner sc = new Scanner(System.in);
System.out.println("作りたい配列の要素数を入力してください");
int n = Integer.parseInt(sc.next()); // 配列要素数
int[] data_array = new int[n]; // 並び替え対象：配列
System.out.println("配列要素数が" + n + "個になるよう各要素に格納する値を入力してください");
for (int i = 0; i < n; i++) {
data_array[i] = Integer.parseInt(sc.next());
}
System.out.println("配列入力結果→" + Arrays.toString(data_array));
int min = 0;
int max = data_array.length - 1;
quickSort(min, max, data_array);
resultPrint(data_array);
} catch (Exception e) {
System.out.println("エラー;" + e.getMessage());// エラーメッセージ表示
e.printStackTrace(); // スタックトレース
}
}
// クイックソートをする、再帰呼び出しされる。
public static void quickSort(int min, int max, int[] data_array) {
int return_value_find_pivot = 0;
int return_value_arrange_array = 0;
return_value_find_pivot = findPivot(min, max, data_array); //基準値を決める
int less_than = 0;
if(return_value_find_pivot != -1){
return_value_arrange_array = arrangeArray(min, max, return_value_find_pivot, data_array); //要素の振り分け
less_than = return_value_arrange_array - 1;
quickSort(min, less_than, data_array); //基準値より未満要素の集まり
quickSort(return_value_arrange_array, max, data_array); //基準値より以上要素の集まり
}else{
return;
}
}
// 基準値を決める。帰り値は基準値の要素番号を返す
public static int findPivot(int min, int max, int[] data_array) {
int return_value = -1;
int compare_min = min + 1;
//minとcompare_min大きい要素番号を探索
while(compare_min <= max){
if(data_array[compare_min] < data_array[min]){
return_value = min;
return return_value; //添字番号を返す
}else if(data_array[compare_min] > data_array[min]){
return_value = compare_min;
return return_value; //添字番号を返す
}
//data_array[compare_min] > data_array[min]ならば、compare_minをインクリメントして再度探索
compare_min++;
}
//配列の要素が全て同じなら-1を返す。
return return_value;
}
// 基準値よりも大きいか小さかを判別する。返り値は基準以上の要素が並んでいる開始要素番号
public static int arrangeArray(int min, int max, int pivot_index, int[] data_array) {
int return_value = 0;
int left = min;
int right = max;
int pivot_value = data_array[pivot_index]; //基準値
while(left < right){
while(data_array[left] < pivot_value){
left++;
if(left >= data_array.length - 1){
break;
}
}
while(data_array[right] >= pivot_value){
right--;
if(right <= 0){
break;
}
}
if(left < right){
swapElement(left, right, data_array);
//left++;
//right--;
}
}
return_value = left;
return return_value;
}
// 引数で受け取った要素番号に応じた要素を入れ替える
public static void swapElement(int left_index, int right_index, int[] data_array) {
int tmp = 0;
tmp = data_array[left_index];
data_array[left_index] = data_array[right_index];
data_array[right_index] = tmp;
}
// 結果の表示
public static void resultPrint(int[] data_array) {
System.out.println("クイックソート結果");
System.out.println(Arrays.toString(data_array));
}
}