再帰処理を使用して配列内の数値を整列させる_2（再帰、クイックソート）
gifu_shino.g再帰処理を使用した例として
整列が高速にできるクイックソートを使ってみます。
クイックソートの簡単な解説とプログラムです。
※この解説では、昇順にすることが前提です。
※ここでは、プログラミングの基礎の習得ということで、
クイックソートをプログラミングをしてみますが、
C言語では、このクイックソートを行う関数が用意され
ていますので、自分でプログラムする必要はありません。
後半で紹介しておきます。
解説です。
1.全要素を２つのブロックに分けるため、
基準値（ピボット）となる要素（値）を決めます。
2.この基準値を基に、この基準値より小さい値を
基準値より前方に、大きい値を基準値より後方に
振り分けます。
※基準値の設定によっては、どちらかに偏って
しまう場合もあります。
※一般に基準値の決め方は、全要素のおおよそ
中央位置にある要素値とします。
3.２分された前方分、後方分の各ブロックから
それぞれの基準値を決定します。
4.前方分、後方分それぞれのブロックで、2.の処理
から繰り返します。
5.各ブロックの要素が１つになった段階で、
そのブロックの整列処理が完了（終了）です。
※この処理により、最初は全体が２ブロックに分割、
次に全体が４ブロックに、次の８ブロックにと
どんどん分割されるともに整列されていきます。
※２分割された前方分、後方分それぞれ、
その後の繰り返し回数は、分割された要素数に
よって、また、基準値の値によって異なります。
いつもなから、学のない私の説明になってしまいました。(-_-;)
この解説を図にしてみます。
次の図では、基準値の値により、各要素の動き（振り分け）が変わる
ことが分かります。
次に図は、実際の配列要素の値によっての動き（振り分け）を
流れを表しています。
次の図は、解説した１ブロックの処理を赤枠で示したものです。
この赤枠の１ブロック分の処理を記述（プログラム）すれば、
他の赤枠の処理も全く同じ流れで処理が可能であることが分かります。
すなわち、再帰処理で処理が可能なことになります。
では、クイックソート法をプログラムしてみます。
・プロジェクトを作成します。
Visual Studio 2022を起動し、
新しいプロジェクトを作成します。
・プロジェクトタイプ："コンソールアプリ"
・プロジェクト名："ct_109_1"
とします。
・プログラム記述・編集画面が表示されるので、
以下のプログラムを記述します。
プログラムの記述内容
// 再帰処理を使用して配列内の数値を整列させる_1（再帰、クイックソート）
#include <iostream>
// プロトタイプ宣言
int quick_sort(int[], int, int);
// メイン関数
int main()
{
// 変数宣言と初期化
int array[] = { 5,1,7,6,4,8,2,10,3,9 };
int num;
// array配列の要素数を取得
num = sizeof(array) / sizeof(array[0]);
// 整列前の配列内数値の表示
printf("整列前 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
// クイックソート関数呼び出し
quick_sort(array, 0, num - 1);
// 整列後の配列内数値の表示
printf("整列後 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
return EXIT_SUCCESS;
}
// クイックソート関数
int quick_sort(int array[], int min_index, int max_index)
{
// 変数宣言
int right, left, middle, work;
// 要素数の確認
if (min_index < max_index) {
// 先頭・末尾・基準値の設定
right = max_index;
left = min_index;
middle = array[(left + right) / 2];
// ブロック内を探索・入れ替えループ
while (left < right) {
// 前方（先頭）から後方へ探索
while (array[left] < middle) {
left = left + 1;
}
// 後方（末尾）から前方へ探索
while (array[right] > middle) {
right = right - 1;
}
// 探索結果の位置関係の確認と入れ替え
if (left < right) {
work = array[left];
array[left] = array[right];
array[right] = work;
}
}
// 再帰呼び出し
quick_sort(array, min_index, left - 1);
quick_sort(array, right + 1, max_index);
}
return 0;
}
簡単なプログラム解説です。
このプログラムは、昇順に整列させるものです。
・プロトタイプ宣言
int quick_sort(int [], int, int);
メイン関数より、メイン関数が呼び出そうとする関数を記述する場合、
呼び出し側より上に記述すれば問題はありませんが、
下に記述した場合には、
コンパイラが、コンパイルビルド時にその関数の確認（認識）が
できず、コンパイルエラーとなってしまいます。
そのため、下に記述する場合には、その関数のシグニチャーが確認
できるよう、プロトタイプ宣言として記述します。
※２つの関数があるとき、この２つの関数がお互いにお互いを呼び出す
ような場合、どちらかの関数を上に記述しても他方の関数が問題になります。
このような場合には、プロトタイプ宣言が必須となります。
※プロトタイプ宣言では、
戻り値の型、関数名、引数の型 を宣言します。
・メイン関数
int main()
{
・変数宣言と初期化
int array[] = { 5,1,7,6,4,8,2,10,3,9 };
整列に使用する未整列値の配列を宣言します。
int num;
配列の要素数を格納するための変数
・array配列の要素数を取得
num = sizeof(array) / sizeof(array[0]);
この式によって、配列内の要素数を取得できます。
・整列前の配列内数値の表示
printf("整列前 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
整列前の要素の値を表示するためのループ処理
・クイックソート関数呼び出し
quick_sort(array, 0, num - 1);
自作の quick_sort( ) 関数を呼び出します。
この時、引数として、
・整列に使用する配列
・整列対象の先頭添え字
・整列対象の末尾添え字
を受け渡します。
・整列後の配列内数値の表示
printf("整列後 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
整列後の要素の値を表示するためのループ処理
return EXIT_SUCCESS;
メイン関数を終了し処理を終了します。
}
・クイックソート関数
int quick_sort(int array[], int min_index, int max_index)
{
・変数宣言
int right, left, middle, work;
right：先頭からの探索位置を格納
left：末尾からの探索位置を格納
middle：基準値を格納
work：値入れ替え時に使用する仮置き用変数
・要素数の確認
if (min_index < max_index) {
ブロック内の要素が２つ以上あるかを確認します。
無ければそのブロック整列処理は不要で、プログラムを
終了します。
・先頭・末尾・基準値の設定
right = max_index;
対象ブロックの先頭要素位置を代入
left = min_index;
対象ブロックの末尾要素位置を代入
middle = array[(left + right) / 2];
対象ブロックの中から基準値を決め、その値を代入
※ここでは、基準値をブロックの中央位置
left + right) / 2 として求めています。
・ブロック内を探索・入れ替えループ
while (left < right) {
前方、後方から探索し、基準値を基に、
それそれの要素が適切な位置に入れ替えられるまで
ループを行います。
・前方（先頭）から後方へ探索
while (array[left] < middle) {
left = left + 1;
}
前方より後方へ順に基準値以上の要素を探索し、
その要素位置を格納します。
※降順に整列する場合、
while (array[left] > middle) {
と修正します。
・後方（末尾）から前方へ探索
while (array[right] > middle) {
right = right - 1;
}
後方より前方へ順に基準値以下の要素を探索し、
その要素位置を格納します。
※降順に整列する場合、
while (array[right] < middle) {
と修正します。
・探索結果の位置関係の確認と入れ替え
if (left < right) {
work = array[left];
array[left] = array[right];
array[right] = work;
}
位置関係が逆転（大＜小）の場合、
その２つの位置の値を入れ替えます。
}
・再帰呼び出し
quick_sort(array, min_index, left - 1);
基準値に基に振り分けられた前方部分を
再び quick_sort( ) 関数に受け渡します。
quick_sort(array,right+1, max_index);
基準値に基に振り分けられた後方部分を
再び quick_sort( ) 関数に受け渡します。
}
return 0;
処理を完了し呼び出し関数へ処理を移します。
}
・実行してみます。
上段メニュー"デバッグ(D)"のサブメニューより、
"デバッグなしで開始(H)"を選択します。
・実行結果は、デバッグコンソール画面が開き表示されます。
※この実行では、整列前の配列内の値と、
整列後の配列内の値を表示しています。
※この画面は、何かのキーを打鍵することで閉じることができます。
プログラミングの学習としてプログラムしてみるには最適なものですが、
実際の業務などでは、記述ミスなども含めて記述するのは面倒です。
C言語では、クイックソートを行うための関数が用意されています。
このクイックソート関数を使ってみます。
関数書式
qsort( 配列名, 要素数, １データのサイズ, 比較方法に使用する関数名 )
となります。
上記のプログラムと同様の処理を行う場合の関数呼び出しは、
qsort(array, sizeof(array) / sizeof(array[0]), sizeof(int), compare_function);
となります。
どのように比較すれば良いか（比較方法に使用する関数）を記述する必要があります。
整数型のデーターを昇順に整列させる場合の比較方法関数の記述例です。
// qsort()での比較方法関数
int compare_function(const void* data1, const void* data2)
{
int num1 = *(int*)data1;
int num2 = *(int*)data2;
return (num1 - num2);
}
配列の前の要素値( num1 )から後ろの要素値( num2 )を引くことで、
昇順指定となります。降順に整列させてい場合、
return (num2 - num1);
とすることで可能になります。
また、型の違うデータの場合は、各設定型をその型に合わせて記述を
変更します。
実数(float)型の場合、
// qsort()での比較方法関数
float compare_function(const void* data1, const void* data2)
{
float num1 = *(float*)data1;
float num2 = *(float*)data2;
return (num1 - num2);
}
と記述を変更すれば完了です。
では、qsort() 関数を使ってプログラムしてみます。
・プロジェクトを作成します。
Visual Studio 2022を起動し、
新しいプロジェクトを作成します。
・プロジェクトタイプ："コンソールアプリ"
・プロジェクト名："ct_109_2"
とします。
・プログラム記述・編集画面が表示されるので、
以下のプログラムを記述します。
プログラムの記述内容
// 再帰処理を使用して配列内の数値を整列させる_2（再帰、クイックソート）
#include <iostream>
// qsort()での比較用関数
int compare_function(const void* data1, const void* data2)
{
int num1 = *(int*)data1;
int num2 = *(int*)data2;
return (num1 - num2);
}
// メイン関数
int main()
{
// 変数宣言と初期化
int array[] = { 5,1,7,6,4,8,2,10,3,9 };
int num;
// array配列の要素数を取得
num = sizeof(array) / sizeof(array[0]);
// 整列前の配列内数値の表示
printf("整列前 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
// ソート関数の利用呼び出し
qsort(array, sizeof(array) / sizeof(array[0]), sizeof(int), compare_function);
// 整列後の配列内数値の表示
printf("整列後 :");
for (int i = 0; i < num; i++) {
printf("%4d", array[i]);
}
printf("\n");
return EXIT_SUCCESS;
}
・実行してみます。
上段メニュー"デバッグ(D)"のサブメニューより、
"デバッグなしで開始(H)"を選択します。
・実行結果は、デバッグコンソール画面が開き表示されます。
※この実行では、整列前の配列内の値と、
整列後の配列内の値を表示しています。
※この画面は、何かのキーを打鍵することで閉じることができます。
・実行結果は、デバッグコンソール画面が開き表示されます。
※この実行では、比較用関数を降順に変更して実行しています。
return (num2 - num1);
整列前の配列内の値と、整列後の配列内の値を表示しています。
