選択範囲の並べ替え - DS チュートリアル

この記事では、選択ソートアルゴリズムについて説明します。選択ソートの作業手順も簡単です。この記事は、試験問題として選択ソートに直面する可能性がある学生にとって、非常に役立ち、興味深いものとなるでしょう。したがって、そのテーマについて話し合うことが重要です。

選択ソートでは、配列のソートされていない要素の中で最小の値がパスごとに選択され、配列内の適切な位置に挿入されます。これは最も単純なアルゴリズムでもあります。これは、インプレース比較並べ替えアルゴリズムです。このアルゴリズムでは、配列は 2 つの部分に分割され、最初はソートされた部分、もう 1 つはソートされていない部分です。最初は、配列のソートされた部分は空で、ソートされていない部分が指定された配列になります。ソートされた部分は左側に配置され、ソートされていない部分は右側に配置されます。

選択ソートでは、ソートされていない配列から最初の最小の要素が選択され、最初の位置に配置されます。その後、2 番目に小さい要素が選択され、2 番目の位置に配置されます。このプロセスは、配列が完全にソートされるまで続行されます。

選択ソートの平均および最悪の場合の複雑さは次のとおりです。 の上²) 、どこ n 項目数です。このため、大規模なデータセットには適していません。

選択ソートは通常、次の場合に使用されます。

小さな配列をソートする必要があります
交換コストは関係ない
すべての要素をチェックすることが必須です

次に、選択ソートのアルゴリズムを見てみましょう。

アルゴリズム

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

選択ソートアルゴリズムの仕組み

ここで、選択ソートアルゴリズムの仕組みを見てみましょう。

選択ソートアルゴリズムの動作を理解するために、ソートされていない配列を取り上げてみましょう。例を使用すると、選択ソートを理解しやすくなります。

配列の要素を次のようにします -

ここで、ソートされた配列の最初の位置について、配列全体が順次スキャンされます。

現在のところ、 12 が最初の位置に格納されており、配列全体を検索した結果、 8 は最小値です。

キーボードにはキーが何個ありますか

したがって、12 を 8 と交換します。最初の反復の後、8 はソートされた配列の最初の位置に表示されます。

現在 29 が格納されている 2 番目の位置については、ソートされていない配列の残りの項目を再度順次スキャンします。スキャン後、配列内で 2 番目に下から 2 番目の要素が 12 であることがわかり、2 番目の位置に表示されるはずです。

ここで、29 を 12 と交換します。2 回目の反復の後、12 はソートされた配列の 2 番目の位置に表示されます。したがって、2 回の反復の後、2 つの最小値がソートされた方法で先頭に配置されます。

同じプロセスが残りの配列要素に適用されます。ここで、選別プロセス全体を図で示します。

これで、配列が完全にソートされました。

選択ソートの複雑さ

ここで、最良のケース、平均的なケース、最悪のケースにおける選択ソートの時間計算量を見てみましょう。選択ソートの空間の複雑さも見ていきます。

1. 時間計算量

場合	時間計算量
最良の場合	の上²)
平均的なケース	の上²)
最悪の場合	の上²)

の上²)

2. 空間の複雑さ

空間の複雑さ	○(1)
安定した	はい

選択ソートの空間計算量は O(1) です。これは、選択ソートでは、入れ替えのために追加の変数が必要になるためです。

選択ソートの実装

次に、さまざまなプログラミング言語での選択ソートのプログラムを見てみましょう。

プログラム： C言語で選択ソートを実装するプログラムを作成します。

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

出力：

プログラム： Java で選択ソートを実装するプログラムを作成します。

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

出力：

上記のコードを実行すると、出力は次のようになります -

それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。

この記事はアルゴリズムだけに限定されたものではありません。また、選択ソートの複雑さ、動作、さまざまなプログラミング言語での実装についても説明しました。