logo

TechCodeview

Utvalgssortering – veiledninger for datastruktur og algoritme

Utvalgssortering er en enkel og effektiv sorteringsalgoritme som fungerer ved å gjentatte ganger velge det minste (eller største) elementet fra den usorterte delen av listen og flytte den til den sorterte delen av listen.

Algoritmen velger gjentatte ganger det minste (eller største) elementet fra den usorterte delen av listen og bytter det med det første elementet i den usorterte delen. Denne prosessen gjentas for den gjenværende usorterte delen til hele listen er sortert.



Hvordan fungerer algoritmen for utvalgssortering?

La oss vurdere følgende array som et eksempel: arr[] = {64, 25, 12, 22, 11}

Første pass:

  • For den første posisjonen i den sorterte matrisen, krysses hele matrisen fra indeks 0 til 4 sekvensielt. Den første posisjonen hvor 64 lagres for øyeblikket, etter å ha krysset hele matrisen er det klart at elleve er den laveste verdien.
  • Erstatt derfor 64 med 11. Etter én iterasjon elleve , som tilfeldigvis er den minste verdien i matrisen, har en tendens til å vises i den første posisjonen i den sorterte listen.

Valg sorteringsalgoritme | Bytter 1. element med minimum i array



Andre pass:

  • For den andre posisjonen, hvor 25 er tilstede, kryss igjen resten av gruppen på en sekvensiell måte.
  • Etter å ha krysset, fant vi det 12 er den nest laveste verdien i matrisen, og den skal vises på andreplass i matrisen, og bytt derfor disse verdiene.

Valg sorteringsalgoritme | bytte i=1 med neste minimumselement

Tredje pass:



  • Nå, for tredjeplassen, hvor 25 er tilstede igjen, krysser resten av matrisen og finner den tredje minste verdien som er tilstede i matrisen.
  • Mens du krysser, 22 kom ut til å være den tredje minste verdien, og den skulle vises på den tredje plassen i matrisen, og dermed bytte 22 med element tilstede i tredje posisjon.

Valg sorteringsalgoritme | bytte i=2 med neste minimumselement

Fjerde pass:

  • På samme måte, for fjerde posisjon, gå gjennom resten av matrisen og finn det fjerde minste elementet i matrisen
  • Som 25 er den fjerde laveste verdien, og vil derfor plasseres på den fjerde posisjonen.

Valg sorteringsalgoritme | bytte i=3 med neste minimumselement

Femte pass:

  • Endelig blir den største verdien som er tilstede i matrisen automatisk plassert på den siste posisjonen i matrisen
  • Den resulterende matrisen er den sorterte matrisen.

Valg sorteringsalgoritme | Nødvendig sortert matrise

Anbefalt praksisutvalg Sorter Prøv det!

Nedenfor er implementeringen av tilnærmingen ovenfor:

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 
// 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 # Bytt minimumselementet som ble funnet med # det første elementet A[i], A[min_idx] = A[min_idx], A[i] # Driverkode for å teste over utskriften ('Sortert array ') for i in range(len(A)): print(A[i],end=' ')>
C# 
// 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); selection_sort($arr, $len); echo 'Sortert array: 
'; for ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>
Produksjon 
Sorted array: 11 12 22 25 64>

Kompleksitetsanalyse av utvalgssortering

Tidskompleksitet: Tidskompleksiteten til utvalgssortering er PÅ 2 ) ettersom det er to nestede løkker:

  • Én sløyfe for å velge et element i Array én etter én = O(N)
  • En annen sløyfe for å sammenligne det elementet med alle andre Array-elementer = O(N)
  • Derfor generell kompleksitet = O(N) * O(N) = O(N*N) = O(N2)

Hjelpeplass: O(1) som det eneste ekstra minnet som brukes er for midlertidige variabler mens du bytter to verdier i Array. Valgsorteringen gjør aldri mer enn O(N)-bytter og kan være nyttig når minneskriving er kostbart.

hvilken samling i java

Fordeler med utvalgssortering

  • Enkelt og lett å forstå.
  • Fungerer godt med små datasett.

Ulemper med algoritmen for utvalgssortering

  • Utvalgssortering har en tidskompleksitet på O(n^2) i verste og gjennomsnittlige tilfelle.
  • Fungerer ikke bra på store datasett.
  • Bevarer ikke den relative rekkefølgen av elementer med like nøkler, noe som betyr at den ikke er stabil.

Ofte stilte spørsmål om utvalgssortering

Q1. Er algoritmen for utvalgssortering stabil?

Standardimplementeringen av algoritmen for utvalgssortering er ikke stabil . Den kan imidlertid gjøres stabil. Vennligst se stabil Utvalg Sortering for detaljer.

Q2. Er algoritmen for utvalgssortering på plass?

Ja, Selection Sort Algorithm er en in-place algoritme, siden den ikke krever ekstra plass.