UDVÆLGELSESSORTERING – DATASTRUKTUR OG ALGORITMEVEJLEDNINGER - TECHCODEVIEW.COM

Udvælgelsessortering er en enkel og effektiv sorteringsalgoritme, der fungerer ved gentagne gange at vælge det mindste (eller største) element fra den usorterede del af listen og flytte det til den sorterede del af listen.

Algoritmen vælger gentagne gange det mindste (eller største) element fra den usorterede del af listen og bytter det ud med det første element i den usorterede del. Denne proces gentages for den resterende usorterede del, indtil hele listen er sorteret.

Hvordan fungerer algoritmen for udvælgelsessortering?

Lad os betragte følgende array som et eksempel: arr[] = {64, 25, 12, 22, 11}

Første pass:

For den første position i det sorterede array gennemløbes hele arrayet fra indeks 0 til 4 sekventielt. Den første position hvor 64 er gemt i øjeblikket, efter at have krydset hele arrayet er det klart, at elleve er den laveste værdi.
Erstat således 64 med 11. Efter én iteration elleve , som tilfældigvis er den mindste værdi i arrayet, har en tendens til at blive vist i den første position på den sorterede liste.

Valg sorteringsalgoritme | Udskiftning af 1. element med minimum i array

Andet pas:

For den anden position, hvor 25 er til stede, skal du igen krydse resten af arrayet på en sekventiel måde.
Efter at have krydset, fandt vi det 12 er den næstlaveste værdi i arrayet, og den bør vises på den anden plads i arrayet, og byt derfor om på disse værdier.

Valg sorteringsalgoritme | at bytte i=1 med det næste minimumselement

Tredje pas:

Nu til tredjepladsen, hvor 25 er til stede igen gennem resten af arrayet og find den tredjemindste værdi til stede i arrayet.
Mens du krydser, 22 kom ud til at være den tredjemindste værdi, og den skulle vises på tredjepladsen i arrayet, således swap 22 med element til stede i tredje position.

Valg sorteringsalgoritme | at bytte i=2 med det næste minimumselement

Fjerde pas:

På samme måde skal du for fjerde position krydse resten af arrayet og finde det fjerde mindste element i arrayet
Som 25 er den 4. laveste værdi, derfor placeres den på den fjerde position.

Valg sorteringsalgoritme | at bytte i=3 med det næste minimumselement

Femte pas:

Endelig bliver den største værdi, der er til stede i arrayet, automatisk placeret på den sidste position i arrayet
Det resulterende array er det sorterede array.

Valg sorteringsalgoritme | Påkrævet sorteret array

Anbefalet praksisvalg Sort Prøv det!

Nedenfor er implementeringen af ovenstående tilgang:

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

 // 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 # Skift det fundne minimumselement med # det første element A[i], A[min_idx] = A[min_idx], A[i] # Driverkode til test over print ('Sorteret array ') for i in range(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

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; } } } // Driverkode $arr = array(64, 25, 12, 22, 11); $len = count($arr); select_sort($arr, $len); echo 'Sorteret array: 
'; for ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Produktion

Sorted array: 11 12 22 25 64>

Kompleksitetsanalyse af udvalgssortering

Tidskompleksitet: Tidskompleksiteten af Selection Sort er PÅ ² ) da der er to indlejrede løkker:

Én sløjfe for at vælge et element i Array én efter én = O(N)
En anden sløjfe til at sammenligne det element med hvert andet Array-element = O(N)
Derfor samlet kompleksitet = O(N) * O(N) = O(N*N) = O(N²)

Hjælpeplads: O(1) som den eneste ekstra hukommelse, der bruges, er til midlertidige variable, mens to værdier udskiftes i Array. Valgsorteringen foretager aldrig mere end O(N)-swaps og kan være nyttig, når hukommelsesskrivning er dyr.

hvordan man derefererer en pointer i c

Fordele ved valgsorteringsalgoritme

Enkel og let at forstå.
Fungerer godt med små datasæt.

Ulemper ved valgsorteringsalgoritmen

Udvælgelsessortering har en tidskompleksitet på O(n^2) i det værste og gennemsnitlige tilfælde.
Fungerer ikke godt på store datasæt.
Bevarer ikke den relative rækkefølge af varer med lige store nøgler, hvilket betyder, at den ikke er stabil.

Ofte stillede spørgsmål om udvalgssortering

Q1. Er udvælgelsessortering-algoritmen stabil?

Standardimplementeringen af udvælgelsessorteringalgoritmen er ikke stabil . Det kan dog gøres stabilt. Se venligst stabilt Udvalg Sort for detaljer.

Q2. Er udvælgelsessorteringalgoritmen på plads?

Ja, Selection Sort Algorithm er en in-place algoritme, da den ikke kræver ekstra plads.

TechCodeview