Pasirinkimo rūšiavimas yra paprastas ir efektyvus rūšiavimo algoritmas, kuris veikia pakartotinai pasirenkant mažiausią (arba didžiausią) elementą iš nerūšiuotos sąrašo dalies ir perkeliant jį į surūšiuotą sąrašo dalį.
Algoritmas pakartotinai pasirenka mažiausią (arba didžiausią) elementą iš nerūšiuotos sąrašo dalies ir pakeičia jį pirmuoju nerūšiuotos dalies elementu. Šis procesas kartojamas likusiai nerūšiuotai daliai, kol visas sąrašas bus surūšiuotas.
Kaip veikia atrankos rūšiavimo algoritmas?
Rekomenduojamos praktikos pasirinkimas Rūšiuoti Išbandykite!Panagrinėkime šį masyvą kaip pavyzdį: arr[] = {64, 25, 12, 22, 11}
Pirmas praėjimas:
- Pirmoje padėtyje surūšiuotame masyve visas masyvas eina nuo indekso 0 iki 4 paeiliui. Pirmoji pozicija, kur 64 yra saugomas šiuo metu, perėjus visą masyvą aišku, kad vienuolika yra mažiausia vertė.
- Taigi 64 pakeiskite 11. Po vienos iteracijos vienuolika , kuri yra mažiausia masyvo reikšmė, paprastai rodoma pirmoje surūšiuoto sąrašo pozicijoje.
Pasirinkimo rūšiavimo algoritmas | 1-ojo elemento keitimas į masyvo minimumą
Antrasis leidimas:
- Antroje pozicijoje, kur yra 25, vėl pereikite likusią masyvo dalį nuosekliai.
- Pervažiavę mes tai radome 12 yra antra mažiausia reikšmė masyve ir ji turėtų būti antroje masyvo vietoje, todėl pakeiskite šias reikšmes.
Pasirinkimo rūšiavimo algoritmas | i=1 pakeitimas kitu minimaliu elementu
Trečias leidimas:
- Dabar dėl trečios vietos, kur 25 vėl yra, pereikite likusią masyvo dalį ir suraskite trečią mažiausią masyve esančią reikšmę.
- Keliaudamas, 22 buvo trečia mažiausia reikšmė ir ji turėtų būti trečioje masyvo vietoje, taigi apsikeisti 22 su elementu trečioje pozicijoje.
Pasirinkimo rūšiavimo algoritmas | i=2 pakeitimas kitu minimaliu elementu
Ketvirtas praėjimas:
- Panašiai, ketvirtoje pozicijoje pereikite likusią masyvo dalį ir suraskite ketvirtą mažiausią masyvo elementą
- Kaip 25 yra 4-a mažiausia vertė, todėl ji bus ketvirtoje pozicijoje.
Pasirinkimo rūšiavimo algoritmas | i=3 pakeitimas kitu minimaliu elementu
Penktas leidimas:
- Pagaliau didžiausia masyve esanti reikšmė automatiškai patenka į paskutinę masyvo poziciją
- Gautas masyvas yra surūšiuotas masyvas.
Pasirinkimo rūšiavimo algoritmas | Reikalingas surūšiuotas masyvas
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
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 # Sukeiskite rastą minimalų elementą # pirmuoju elementu A[i], A[min_idx] = A[min_idx], A[i] # Tvarkyklės kodas, kurį norite išbandyti virš spausdinimo ('Sorted array ') i diapazone(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>>
Išvestis Laiko sudėtingumas: Atrankos rūšiavimo laiko sudėtingumas yra O (N 2 ) nes yra dvi įdėtos kilpos: - Viena kilpa masyvo elementui pasirinkti po vieną = O (N)
- Kita kilpa, skirta palyginti šį elementą su kiekvienu kitu masyvo elementu = O (N)
- Todėl bendras sudėtingumas = O(N) * O(N) = O(N*N) = O(N2)
Pagalbinė erdvė: O (1) kaip vienintelė naudojama papildoma atmintis skirta laikiniesiems kintamiesiems keičiant dvi masyvo reikšmes. Pasirinkimo rūšiavimas niekada neatlieka daugiau nei O(N) apsikeitimų ir gali būti naudingas, kai įrašymas į atmintį yra brangus.
cm iki pėdų ir colių
Pasirinkimo rūšiavimo algoritmo privalumai
- Paprasta ir lengvai suprantama.
- Puikiai veikia su mažais duomenų rinkiniais.
Pasirinkimo rūšiavimo algoritmo trūkumai
- Pasirinkimo rūšiavimo laiko sudėtingumas yra O(n^2) blogiausiu ir vidutiniu atveju.
- Neveikia gerai su dideliais duomenų rinkiniais.
- Neišsaugo santykinės daiktų tvarkos su vienodais klavišais, vadinasi, ji nėra stabili.
Dažnai užduodami klausimai apie atrankos rūšiavimą
Q1. Ar atrankos rūšiavimo algoritmas stabilus?
Numatytasis pasirinkimo rūšiavimo algoritmo įgyvendinimas yra nėra stabilus . Tačiau jis gali būti stabilus. Prašome žiūrėti stabilus atrankos rūšiavimas dėl detalių.
Q2. Ar pasirinktas rūšiavimo algoritmas?
Taip, pasirinkimo rūšiavimo algoritmas yra vietoje algoritmas, nes jam nereikia papildomos vietos.