選択の並べ替え – データ構造とアルゴリズムのチュートリアル - TECHCODEVIEW.COM

選択の並べ替え は、リストの未ソート部分から最小 (または最大) の要素を繰り返し選択し、それをリストのソート済み部分に移動する、シンプルで効率的なソートアルゴリズムです。

このアルゴリズムは、リストの未ソート部分から最小 (または最大) 要素を繰り返し選択し、それを未ソート部分の最初の要素と交換します。このプロセスは、リスト全体がソートされるまで、残りの未ソート部分に対して繰り返されます。

選択ソートアルゴリズムはどのように機能しますか?

例として次の配列を考えてみましょう。 arr[] = {64, 25, 12, 22, 11}

最初のパス:

ソートされた配列の最初の位置では、配列全体がインデックス 0 から 4 まで順番に走査されます。最初の位置は、 64 は現在保存されており、配列全体を走査した後、次のことが明らかです。十一は最低値です。
したがって、64 を 11 に置き換えます。 1 回の反復後十一配列内の最小値であるは、ソートされたリストの最初の位置に表示される傾向があります。

選択ソートアルゴリズム |最初の要素を配列の最小値と交換する

2 番目のパス:

25 が存在する 2 番目の位置では、配列の残りの部分を再度順次走査します。
横断してわかったのは、 12 は配列内で 2 番目に小さい値であり、配列内の 2 番目の位置に表示される必要があるため、これらの値を交換します。

選択ソートアルゴリズム | i=1 を次の最小要素と交換する

3回目のパス:

さて、3位はどこですか 25 存在する場合は、配列の残りの部分を再度走査し、配列内に存在する 3 番目に小さい値を見つけます。
横断中、 22 は 3 番目に小さい値であることが判明し、配列の 3 番目の場所に表示されるはずなので、交換します。 22 要素が 3 番目の位置に存在します。

選択ソートアルゴリズム | i=2 を次の最小要素と交換する

4 番目のパス:

同様に、4 番目の位置については配列の残りの部分を走査し、配列内の 4 番目に小さい要素を見つけます。
として 25 は 4 番目に低い値であるため、4 番目の位置に配置されます。

選択ソートアルゴリズム | i=3 を次の最小要素と交換します

5 番目のパス:

最後に、配列内に存在する最大値が自動的に配列内の最後の位置に配置されます。
結果の配列はソートされた配列です。

選択ソートアルゴリズム |必須のソートされた配列

おすすめ練習セレクション並べ替え試してみる！

上記のアプローチの実装を以下に示します。

C++

 // C++ program for implementation of // selection sort #include  using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of  // unsorted subarray  for (i = 0; i < n - 1; i++) {  // Find the minimum element in  // unsorted array  min_idx = i;  for (j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx])  min_idx = j;  }  // Swap the found minimum element  // with the first element  if (min_idx != i)  swap(arr[min_idx], arr[i]);  } } // Function to print an array void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++) {  cout << arr[i] << ' ';  cout << endl;  } } // Driver program int main() {  int arr[] = { 64, 25, 12, 22, 11 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  selectionSort(arr, n);  cout << 'Sorted array: 
';  printArray(arr, n);  return 0; } // This is code is contributed by rathbhupendra>

 // C program for implementation of selection sort #include  void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of unsorted subarray  for (i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  min_idx = i;  for (j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first element  if(min_idx != i)  swap(&arr[min_idx], &arr[i]);  } } /* Function to print an array */ void printArray(int arr[], int size) {  int i;  for (i=0; i < size; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver program to test above functions int main() {  int arr[] = {64, 25, 12, 22, 11};  int n = sizeof(arr)/sizeof(arr[0]);  selectionSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>

ジャワ

 // Java program for implementation of Selection Sort import java.io.*; public class SelectionSort {  void sort(int arr[])  {  int n = arr.length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  void printArray(int arr[])  {  int n = arr.length;  for (int i=0; i

Python3

 # Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining  # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # 見つかった最小要素を # 最初の要素と交換します A[i], A[min_idx] = A[min_idx], A[i] # 上記をテストするドライバー コード print ('ソートされた配列') for i in range(len(A)): print(A[i],end=' ')>>'C#

JavaScript

>>

PHP

  // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$low]; $arr[$low] = $tmp; } } } // ドライバーコード $arr = array(64, 25, 12, 22, 11); $len = カウント($arr);選択ソート($arr, $len); echo 'ソートされた配列 : 
'; for ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>>

出力

Sorted array: 11 12 22 25 64>

選択ソートの複雑さの分析

時間計算量: 選択ソートの時間計算量は次のとおりです。の上 ² ) 入れ子になったループが 2 つあるためです。

配列の要素を 1 つずつ選択する 1 つのループ = O(N)
その要素を他のすべての配列要素と比較する別のループ = O(N)
したがって、全体的な複雑さ = O(N) * O(N) = O(N*N) = O(N²)

補助スペース: O(1) は、配列内の 2 つの値を交換する際の一時変数用に使用される唯一の追加メモリです。選択ソートは O(N) を超えるスワップを行わないため、メモリ書き込みにコストがかかる場合に役立ちます。

対称的な差

選択ソートアルゴリズムの利点

シンプルでわかりやすい。
小規模なデータセットに適しています。

選択ソートアルゴリズムの欠点

選択ソートの時間計算量は、最悪の平均的なケースでも O(n^2) になります。
大規模なデータセットではうまく機能しません。
等しいキーを持つ項目の相対的な順序は保持されないため、安定していません。

選択並べ替えに関するよくある質問

Q1.選択ソートアルゴリズムは安定していますか?

選択ソートアルゴリズムのデフォルトの実装は次のとおりです。 不安定 。ただし、安定させることは可能です。をご覧ください。安定した選択ソート詳細については。

Q2.選択ソートアルゴリズムは導入されていますか?

はい、選択並べ替えアルゴリズムは追加のスペースを必要としないため、インプレースアルゴリズムです。

TechCodeview