selection sort c with examples
例を使用したC ++での選択ソートの詳細。
名前自体が示すように、選択ソート手法では、最初に配列内の最小の要素を選択し、それを配列内の最初の要素と交換します。
次に、配列内の2番目に小さい要素を2番目の要素と交換します。したがって、パスごとに、配列内の最小の要素が選択され、配列全体が並べ替えられるまで適切な位置に配置されます。
=> ここで完璧なC ++トレーニングガイドをチェックしてください。
学習内容：
前書き
選択ソートは、すべてのパスで最小の要素を見つけて正しい位置に配置するだけなので、非常に簡単なソート手法です。
選択ソートは、ソートするリストのサイズが小さい場合に効率的に機能しますが、ソートするリストのサイズが大きくなると、パフォーマンスに大きな影響を与えます。
したがって、データのリストが大きい場合は、選択ソートはお勧めできません。
一般的なアルゴリズム
選択ソートの一般的なアルゴリズムを以下に示します。
Chromeに最適な広告ブロック拡張機能
選択ソート（A、N）
ステップ1 ：K = 1からN-1について、手順2と3を繰り返します。
ステップ2 ：ルーチンsmallest（A、K、N、POS）を呼び出す
ステップ3 ：A (K)をA (POS)と交換します
(ループの終わり)
ステップ4 ： 出口
ルーチン最小（A、K、N、POS）
- ステップ1 ：(初期化) setsmallestElem = A (K)
- ステップ2 ：(初期化) POS = Kに設定
- ステップ3 ：J = K +1からN-1の場合、繰り返します
最小の場合Elem> A (J)
最小値を設定Elem = A (J)
POS = Jに設定
(終了した場合)
(ループの終わり) - ステップ4 ：POSを返す
選択ソートの擬似コード
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) この選択ソートアルゴリズムを説明する例を以下に示します。
図
この図の表形式の表現を以下に示します。
ソートされていないリスト 最小要素 ソート済みリスト {18,10,7,20,2} 二 {} {18,10,7,20} 7 {二} {18,10,20} 10 {2.7} {18.20} 18 {2,7,10） {20} 20 {2,7,10,18} {} {2,7,10,18,20}
図から、パスごとに、次に小さい要素がソートされた配列の正しい位置に配置されていることがわかります。上の図から、5つの要素の配列を並べ替えるには、4つのパスが必要であることがわかります。つまり、一般に、N個の要素の配列を並べ替えるには、合計でN-1回のパスが必要です。
以下に示すのは、C ++での選択ソートアルゴリズムの実装です。
C ++の例
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<10;i++) { cout< 出力：
ソートする要素の入力リスト
11 5 2 20 42 53 23 34101 22
要素のソートされたリストは
2 5 11 20 22 23 34 42 53101
配列の並べ替えに必要なパスの数：10
上記のプログラムに示されているように、配列の最初の要素を配列の他のすべての要素と比較することから、選択ソートを開始します。この比較の最後に、配列内の最小の要素が最初の位置に配置されます。
次のパスでは、同じアプローチを使用して、配列内で次に小さい要素が正しい位置に配置されます。これは、N個の要素まで、または配列全体が並べ替えられるまで続きます。
Javaの例
次に、Java言語で選択ソート手法を実装します。
class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println('
Input list to be sorted...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println('
printing sorted elements...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j) 出力：
ソートする入力リスト…
11 5 2 20 42 53 23 34101 22
ソートされた要素の印刷…
2 5 11 20 22 23 34 42 53101
上記のJavaの例でも、同じロジックを適用します。配列内で最小の要素を繰り返し検索し、配列全体が完全に並べ替えられるまで、並べ替えられた配列に配置します。
したがって、選択ソートは、配列内で次に小さい要素を繰り返し見つけて、適切な位置にある要素と交換するだけなので、実装するのに最も簡単なアルゴリズムです。
選択ソートの複雑さの分析
上記の選択ソートの擬似コードに見られるように、選択ソートがそれ自体を完了するには、互いにネストされた2つのforループが必要であることがわかっています。 1つのforループは配列内のすべての要素をステップスルーし、外側のforループ内にネストされている別のforループを使用して最小要素インデックスを見つけます。
したがって、入力配列のサイズNが与えられると、選択ソートアルゴリズムには次の時間と複雑さの値があります。
最悪の場合の時間計算量 O（n 2）; O（n）スワップ ベストケースの時間計算量 O（n 2）; O（n）スワップ 平均時間計算量 O（n 2）; O（n）スワップ スペースの複雑さ O（1）
O（の時間計算量 n 二）は主に2つのforループを使用しているためです。選択ソート手法は、O（n）スワップを超えることはなく、メモリ書き込み操作にコストがかかることが判明した場合に役立ちます。
結論
選択ソートは、簡単に実装できるもう1つの最も単純なソート手法です。選択ソートは、ソートされる値の範囲がわかっている場合に最適に機能します。したがって、選択ソートを使用したデータ構造のソートに関する限り、線形で有限サイズのデータ構造のみをソートできます。
これは、選択ソートを使用して、配列などのデータ構造を効率的にソートできることを意味します。
このチュートリアルでは、C ++およびJava言語を使用した選択ソートの実装を含め、選択ソートについて詳しく説明しました。選択ソートの背後にあるロジックは、リスト内の最小の要素を繰り返し見つけて、適切な位置に配置することです。
次のチュートリアルでは、これまでに説明した他の2つの手法、つまりバブルソートと選択ソートよりも効率的な手法であると言われている挿入ソートについて詳しく学習します。
=> ここでC ++トレーニングチュートリアルのA-Zを確認するには、ここをクリックしてください。
推奨読書
