Sortowanie przez wybór to prosty i wydajny algorytm sortowania, który polega na wielokrotnym wybieraniu najmniejszego (lub największego) elementu z nieposortowanej części listy i przenoszeniu go do posortowanej części listy.

Algorytm wielokrotnie wybiera najmniejszy (lub największy) element z nieposortowanej części listy i zamienia go z pierwszym elementem nieposortowanej części. Proces ten jest powtarzany dla pozostałej nieposortowanej części, aż do posortowania całej listy.

Jak działa algorytm sortowania przez wybór?

Rozważmy jako przykład następującą tablicę: tablica [] = {64, 25, 12, 22, 11}

Pierwsze przejście:

• Dla pierwszej pozycji posortowanej tablicy cała tablica jest przemierzana sekwencyjnie od indeksu 0 do 4. Pierwsza pozycja gdzie 64 jest aktualnie przechowywany, po przejściu całej tablicy staje się to jasne jedenaście jest najniższą wartością.
• Zatem zamień 64 na 11. Po jednej iteracji jedenaście , która jest najmniejszą wartością w tablicy, zwykle pojawia się na pierwszej pozycji posortowanej listy.

Algorytm sortowania przez wybór | Zamiana pierwszego elementu na minimum w tablicy

Drugie przejście:

• Dla drugiej pozycji, gdzie występuje 25, ponownie przejdź przez resztę tablicy w sposób sekwencyjny.
• Po przejściu znaleźliśmy to 12 jest drugą najniższą wartością w tablicy i powinna pojawić się na drugim miejscu w tablicy, w związku z czym zamień te wartości.

Algorytm sortowania przez wybór | zamiana i=1 na następny element minimalny

Trzecie przejście:

• Teraz o trzecie miejsce, gdzie 25 jest obecny, przejrzyj resztę tablicy i znajdź trzecią najmniejszą wartość obecną w tablicy.
• Podczas przemierzania, 22 okazała się trzecią najmniejszą wartością i powinna pojawić się na trzecim miejscu w tablicy, w ten sposób zamień 22 z elementem obecnym na trzeciej pozycji.

Algorytm sortowania przez wybór | zamiana i=2 na następny element minimalny

Czwarte przejście:

• Podobnie dla czwartej pozycji przejdź przez resztę tablicy i znajdź czwarty najmniejszy element w tablicy
• Jak 25 jest czwartą najniższą wartością, dlatego zajmie czwartą pozycję.

Algorytm sortowania przez wybór | zamiana i=3 na następny element minimalny

Piąta przepustka:

• W końcu największa wartość występująca w tablicy jest automatycznie umieszczana na ostatniej pozycji w tablicy
• Wynikowa tablica jest tablicą posortowaną.

Algorytm sortowania przez wybór | Wymagana posortowana tablica

Poniżej implementacja powyższego podejścia:

// 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

# 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 # Zamień znaleziony element minimalny na # pierwszy element A[i], A[min_idx] = A[min_idx], A[i] # Kod sterownika do przetestowania powyżej wydruku ('Tablica posortowana ') dla i w zakresie(len(A)): print(A[i],end=' ')>

// C# program for implementation  // of Selection Sort using System; class GFG {   static 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  static void printArray(int []arr)  {  int n = arr.Length;  for (int i=0; i

>

 // 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[$niski]) { $tmp = $arr[$i]; $arr[$i] = $arr[$niski]; $arr[$niski] = $tmp; } } } // Kod sterownika $arr = array(64, 25, 12, 22, 11); $len = liczba($arr); selekcja_sort($arr, $len); echo 'Posortowana tablica: 
'; dla ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Analiza złożoności sortowania przez wybór

Złożoność czasowa: Złożoność czasowa sortowania przez wybór wynosi NA ² ) ponieważ istnieją dwie zagnieżdżone pętle:

• Jedna pętla do wybierania elementów tablicy jeden po drugim = O(N)
• Kolejna pętla porównująca ten element z każdym innym elementem Array = O(N)
• Zatem ogólna złożoność = O(N) * O(N) = O(N*N) = O(N²)

Przestrzeń pomocnicza: O(1), ponieważ jedyna dodatkowa pamięć używana jest dla zmiennych tymczasowych podczas zamiany dwóch wartości w tablicy. Sortowanie przez wybór nigdy nie powoduje więcej niż O(N) zamian i może być przydatne, gdy zapisywanie w pamięci jest kosztowne.

listonosz

Zalety algorytmu sortowania przez wybór

• Proste i łatwe do zrozumienia.
• Działa dobrze z małymi zbiorami danych.

Wady algorytmu sortowania przez wybór

• Sortowanie przez wybór ma złożoność czasową O(n^2) w najgorszym i średnim przypadku.
• Nie działa dobrze w przypadku dużych zbiorów danych.
• Nie zachowuje względnej kolejności elementów z równymi kluczami, co oznacza, że ​​nie jest stabilna.

Często zadawane pytania dotyczące sortowania przez wybór

Pytanie 1. Czy algorytm sortowania przez wybór jest stabilny?

Domyślna implementacja algorytmu sortowania przez wybór to niestabilny . Można go jednak uczynić stabilnym. Proszę zobaczyć stabilne sortowanie przez wybór dla szczegółów.

Pytanie 2. Czy działa algorytm sortowania przez wybór?

Tak, algorytm sortowania przez wybór jest algorytmem lokalnym, ponieważ nie wymaga dodatkowej przestrzeni.