この記事では、選択ソート アルゴリズムについて説明します。選択ソートの作業手順も簡単です。この記事は、試験問題として選択ソートに直面する可能性がある学生にとって、非常に役立ち、興味深いものとなるでしょう。したがって、そのテーマについて話し合うことが重要です。
選択ソートでは、配列のソートされていない要素の中で最小の値がパスごとに選択され、配列内の適切な位置に挿入されます。これは最も単純なアルゴリズムでもあります。これは、インプレース比較並べ替えアルゴリズムです。このアルゴリズムでは、配列は 2 つの部分に分割され、最初はソートされた部分、もう 1 つはソートされていない部分です。最初は、配列のソートされた部分は空で、ソートされていない部分が指定された配列になります。ソートされた部分は左側に配置され、ソートされていない部分は右側に配置されます。
選択ソートでは、ソートされていない配列から最初の最小の要素が選択され、最初の位置に配置されます。その後、2 番目に小さい要素が選択され、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 > 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) |
| 平均的なケース | の上2) |
| 最悪の場合 | の上2) |
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] > 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 = ' ') a = [69, 14, 1, 50, 59] print('Before sorting array elements are - ') printArr(a) selection(a) print('
After sorting array elements are - ') 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>'; printArray($a, $n); selection($a, $n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </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'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>'; printArray($a, $n); selection($a, $n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </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'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;> 出力：
上記のコードを実行すると、出力は次のようになります -
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。
この記事はアルゴリズムだけに限定されたものではありません。また、選択ソートの複雑さ、動作、さまざまなプログラミング言語での実装についても説明しました。