Selectie sorteren is een eenvoudig en efficiënt sorteeralgoritme dat werkt door herhaaldelijk het kleinste (of grootste) element uit het ongesorteerde deel van de lijst te selecteren en dit naar het gesorteerde deel van de lijst te verplaatsen.

Het algoritme selecteert herhaaldelijk het kleinste (of grootste) element uit het ongesorteerde deel van de lijst en verwisselt dit met het eerste element van het ongesorteerde deel. Dit proces wordt herhaald voor het resterende ongesorteerde deel totdat de hele lijst is gesorteerd.

Hoe werkt het selectiesorteeralgoritme?

Laten we de volgende array als voorbeeld beschouwen: arr[] = {64, 25, 12, 22, 11}

Eerste Paas:

• Voor de eerste positie in de gesorteerde array wordt de hele array opeenvolgend doorlopen van index 0 tot en met 4. De eerste positie waar 64 wordt momenteel opgeslagen, na het doorlopen van de hele array is het duidelijk dat elf is de laagste waarde.
• Vervang dus 64 door 11. Na één iteratie elf , wat toevallig de minste waarde in de array is, verschijnt meestal op de eerste positie van de gesorteerde lijst.

Selectie Sorteeralgoritme | Het eerste element verwisselen met het minimum in de array

Tweede pas:

• Voor de tweede positie, waar 25 aanwezig is, doorkruist u opnieuw de rest van de array op een sequentiële manier.
• Na het doorkruisen vonden we dat 12 is de op een na laagste waarde in de array en zou op de tweede plaats in de array moeten verschijnen, dus verwissel deze waarden.

Selectie Sorteeralgoritme | i = 1 verwisselen met het volgende minimumelement

Derde pas:

• Nu, voor de derde plaats, waar 25 aanwezig is, doorloopt u opnieuw de rest van de array en vindt u de derde kleinste waarde die in de array aanwezig is.
• Tijdens het doorkruisen, 22 bleek de derde laagste waarde te zijn en deze zou op de derde plaats in de array moeten verschijnen, dus swap 22 met element aanwezig op de derde positie.

Selectie Sorteeralgoritme | i = 2 verwisselen met het volgende minimumelement

Vierde pas:

• Op dezelfde manier doorkruist u voor de vierde positie de rest van de array en vindt u het vierde kleinste element in de array
• Als 25 is de vierde laagste waarde en komt daarom op de vierde positie terecht.

Selectie Sorteeralgoritme | i = 3 verwisselen met het volgende minimumelement

Vijfde pas:

• Eindelijk wordt de grootste waarde in de array automatisch op de laatste positie in de array geplaatst
• De resulterende array is de gesorteerde array.

Selectie Sorteeralgoritme | Vereiste gesorteerde array

Hieronder vindt u de implementatie van de bovenstaande aanpak:

// 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 # Verwissel het gevonden minimumelement met # het eerste element A[i], A[min_idx] = A[min_idx], A[i] # Stuurprogrammacode om te testen hierboven print ('Gesorteerde array ') voor i binnen bereik(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[$laag]) { $tmp = $arr[$i]; $arr[$i] = $arr[$laag]; $arr[$laag] = $tmp; } } } // Stuurprogrammacode $arr = array(64, 25, 12, 22, 11); $len = aantal($arr); selectie_sort($arr, $len); echo 'Gesorteerde array: 
'; voor ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

Sorted array: 11 12 22 25 64>

Complexiteitsanalyse van selectiesortering

Tijdcomplexiteit: De tijdscomplexiteit van Selectie Sorteren is OP ² ) omdat er twee geneste lussen zijn:

• Eén lus om een ​​element van Array één voor één te selecteren = O(N)
• Nog een lus om dat element te vergelijken met elk ander Array-element = O(N)
• Daarom is de totale complexiteit = O(N) * O(N) = O(N*N) = O(N).²)

Hulpruimte: O(1) omdat het enige extra geheugen dat wordt gebruikt, bedoeld is voor tijdelijke variabelen tijdens het verwisselen van twee waarden in Array. De selectiesortering maakt nooit meer dan O(N)-swaps en kan handig zijn als het schrijven van geheugen kostbaar is.

linkedlist en arraylist

Voordelen van selectie-sorteeralgoritme

• Eenvoudig en gemakkelijk te begrijpen.
• Werkt goed met kleine datasets.

Nadelen van het selectiesorteeralgoritme

• Selectiesortering heeft in het slechtste en gemiddelde geval een tijdscomplexiteit van O(n^2).
• Werkt niet goed op grote datasets.
• Behoudt de relatieve volgorde van items met gelijke sleutels niet, wat betekent dat deze niet stabiel is.

Veelgestelde vragen over Selectie Sorteren

Q1. Is het selectiesorteeralgoritme stabiel?

De standaardimplementatie van het selectiesorteeralgoritme is niet stabiel . Het kan echter stabiel worden gemaakt. Zie de stabiele selectiesortering voor details.

Vraag 2. Is het selectiesorteeralgoritme aanwezig?

Ja, het selectiesorteeralgoritme is een in-place algoritme, omdat er geen extra ruimte voor nodig is.