C++での再帰的選択ソート

選択ソートは、配列を最初から繰り返し、各要素をリスト内の最小の要素に置き換えることによってデータをソートするために使用されるソートアルゴリズムの1つです。先に進むと、左側の配列が並べ替えられ、右側の配列は並べ替えられません。移動するたびに、スワッピングによってインデックスの現在の位置に次に小さいものが配置されます。

選択ソートアルゴリズム

• int arr [5] ={5,4,2,1,3};

• int i、j;

• インデックスi=0からi<配列サイズ-1

  までトラバースします

  • インデックスj=i+1から配列サイズ-1までトラバースします

  • 最小のものを見つけて、そのindex.posを保存します

• 見つかったインデックス位置の要素をarr[i]

  と交換します

• 終了

再帰的選択ソート

• 最小要素のインデックスを見つける

• 見つかった最小の要素インデックスが配列サイズと等しい場合は、戻ります。

• それ以外の場合は、現在の要素を最小の要素と交換します

• ソートされた要素を除く残りの配列に対して、上記の手順を再帰的に実行します

例

入力 − arr [] ={5,7,2,3,1,4};長さ=6

出力 −ソートされた配列：1 2 3 4 5 7

説明 −

First Pass :-
5 7 2 3 1 4 → swap → 1 2 7 3 5 4
1 2 7 3 5 4 → no swap
1 2 7 3 5 4 → swap → 1 2 3 7 5 4
1 2 3 7 5 4 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 → no swap

入力 − arr [] ={1、2、3、3、2};

出力 −ソートされた配列：1 2 2 3 3

説明 −

1 2 3 3 2 → no swap
1 2 3 2 3 → no swap
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 → no swap

以下のプログラムで使用されているアプローチは次のとおりです

選択ソートの再帰的アプローチでは、基本ケースは最小インデックス=配列サイズ-1です。それ以外の場合は、現在のインデックスとの配列スワップから最小値を見つけ、ソートされていない配列を再帰的にソートします。

• 入力配列Arr[]と長さをその中の要素の数とします。

• 関数findMin（int arr []、int i、int j）は、配列とそのインデックスを取得し、arr [i+1]からarr[j]までの最小要素のインデックスを返します。

• 可変ミンポを取ります。

• iとjの両方が同じである場合、両方が同じであるため、最小要素のインデックスとしてiを返します。

• それ以外の場合、再帰的にminpos =findMin（arr、i + 1、j）を使用して位置i+1からjを探します。

• if（arr [i]

• 関数recurselectSort（int arr1 []、int len1、int pos1）は入力配列を受け取り、選択ソートの再帰を使用して昇順でソートします。

• pos1 ==len1の場合、最小値が見つからない場合は、戻ります。

• それ以外の場合は、minpos1 =findMin（arr1、pos1、len1-1）

  を設定します。

• 現在のpos1インデックスと最小要素インデックスminpos1が同じでない場合は、tempを使用してこれらのインデックスの要素を交換します。

• recurselectSort（arr1、len1、pos1 + 1）を使用して、配列の残りの部分を再帰します。

• すべての呼び出しの最後に、lenが1になると、再帰が終了し、配列が並べ替えられます。

• ソートされた配列をmain内に出力します。

例

#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
   int minpos;
   if (i == j){
      return i;
   }
   minpos = findMin(arr, i + 1, j);
   if(arr[i]<arr[minpos]){
      minpos=i;
   }
   return (minpos);
}
void recurselectSort(int arr1[], int len1, int pos1){
   int temp;
   int minpos1;
   if (pos1 == len1){
      return;
   }
   minpos1 = findMin(arr1, pos1, len1-1);
   if (minpos1 != pos1){
      temp=arr1[pos1];
      arr1[pos1]=arr1[minpos1];
      arr1[minpos1]=temp;
   }
   recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
   int Arr[] = {1,5,3,0,9,3,5};
   int length = sizeof(Arr)/sizeof(Arr[0]);
   recurselectSort(Arr,length,0);
   cout<<"Sorted Array using recursive Selection sort: "<<endl;
   for (int i = 0; i<length ; i++){
      cout << Arr[i] << " ";
   }
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Sorted Array using recursive Selection sort:
0 1 3 3 5 5 9