Urvalssortering är en enkel och effektiv sorteringsalgoritm som fungerar genom att upprepade gånger välja det minsta (eller största) elementet från den osorterade delen av listan och flytta den till den sorterade delen av listan.
Algoritmen väljer upprepade gånger det minsta (eller största) elementet från den osorterade delen av listan och byter ut det med det första elementet i den osorterade delen. Denna process upprepas för den återstående osorterade delen tills hela listan är sorterad.
Hur fungerar algoritm för urvalssortering?
Rekommenderat övningsval Sortera Prova!Låt oss betrakta följande array som ett exempel: arr[] = {64, 25, 12, 22, 11}
Första passet:
- För den första positionen i den sorterade arrayen genomkorsas hela arrayen från index 0 till 4 sekventiellt. Den första positionen där 64 lagras för närvarande, efter att ha korsat hela arrayen är det tydligt att elva är det lägsta värdet.
- Ersätt alltså 64 med 11. Efter en iteration elva , som råkar vara det minsta värdet i arrayen, tenderar att visas i den första positionen i den sorterade listan.
Urval Sorteringsalgoritm | Byter 1:a element med minimum i array
Andra passet:
- För den andra positionen, där 25 är närvarande, genomkorsar du återigen resten av arrayen på ett sekventiellt sätt.
- Efter att ha korsat hittade vi det 12 är det näst lägsta värdet i arrayen och det bör visas på andra plats i arrayen, byt därför ut dessa värden.
Urval Sorteringsalgoritm | byta i=1 med nästa minimumelement
Tredje passet:
- Nu, för tredje plats, var 25 är närvarande genomkorsar återigen resten av arrayen och hittar det tredje minsta värdet som finns i arrayen.
- När du korsar, 22 kom ut att vara det tredje minsta värdet och det borde visas på tredje plats i arrayen, alltså swap 22 med element närvarande i tredje position.
Urval Sorteringsalgoritm | byta i=2 med nästa minimielement
Fjärde passet:
- På samma sätt, för fjärde position, gå igenom resten av arrayen och hitta det fjärde minsta elementet i arrayen
- Som 25 är det fjärde lägsta värdet och kommer därför att placeras på fjärde positionen.
Urval Sorteringsalgoritm | byta i=3 med nästa minimumelement
Femte passet:
- Äntligen placeras det största värdet som finns i arrayen automatiskt på den sista positionen i arrayen
- Den resulterande arrayen är den sorterade arrayen.
Urval Sorteringsalgoritm | Krävs sorterad array
Nedan är implementeringen av ovanstående tillvägagångssätt:
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 # Byt ut det minsta elementet som hittades med # det första elementet A[i], A[min_idx] = A[min_idx], A[i] # Drivrutinskod för att testa ovanför utskrift ('Sorterad array ') för i inom intervallet(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[$låg]; $arr[$low] = $tmp; } } } // Drivrutinskod $arr = array(64, 25, 12, 22, 11); $len = count($arr); selection_sort($arr, $len); echo 'Sorterad array:
'; för ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed // by Deepika Gupta. ?>> Produktion
Sorted array: 11 12 22 25 64>
Komplexitetsanalys av urvalssort
Tidskomplexitet: Tidskomplexiteten för urvalssortering är PÅ 2 ) eftersom det finns två kapslade slingor:
- En slinga för att välja ett element i Array en efter en = O(N)
- Ytterligare en slinga för att jämföra det elementet med alla andra Array-element = O(N)
- Därför total komplexitet = O(N) * O(N) = O(N*N) = O(N2)
Hjälputrymme: O(1) som det enda extra minnet som används är för temporära variabler samtidigt som man byter två värden i Array. Valsorteringen gör aldrig mer än O(N)-byten och kan vara användbar när minnesskrivning är kostsamt.
världens bästa leende
Fördelar med urvalssorteringsalgoritm
- Enkelt och lätt att förstå.
- Fungerar bra med små dataset.
Nackdelar med urvalssorteringsalgoritmen
- Urvalssortering har en tidskomplexitet på O(n^2) i det värsta och genomsnittliga fallet.
- Fungerar inte bra på stora datamängder.
- Bevarar inte den relativa ordningen för objekt med lika nycklar vilket betyder att den inte är stabil.
Vanliga frågor om urvalssortering
Q1. Är urvalssorteringsalgoritmen stabil?
Standardimplementeringen av urvalssorteringsalgoritmen är inte stabil . Den kan dock göras stabil. Vänligen se stabil Urval Sortera för detaljer.
Q2. Är algoritm för urvalssortering på plats?
Ja, algoritm för urvalssortering är en algoritm på plats, eftersom den inte kräver extra utrymme.