Valinnan lajittelu on yksinkertainen ja tehokas lajittelualgoritmi, joka toimii valitsemalla toistuvasti pienimmän (tai suurimman) elementin luettelon lajittelemattomasta osasta ja siirtämällä sen luettelon lajiteltuun osaan.
Algoritmi valitsee toistuvasti pienimmän (tai suurimman) elementin luettelon lajittelemattomasta osasta ja vaihtaa sen lajittelemattoman osan ensimmäisen elementin kanssa. Tätä prosessia toistetaan jäljellä olevan lajittelemattoman osan osalta, kunnes koko luettelo on lajiteltu.
Kuinka valintalajittelualgoritmi toimii?
Suositeltu harjoitusvalikoima Lajittele Kokeile!Tarkastellaan seuraavaa taulukkoa esimerkkinä: arr[] = {64, 25, 12, 22, 11}
Ensimmäinen läpimeno:
- Ensimmäistä sijaintia varten lajitetussa taulukossa koko taulukko kulkee indeksistä 0 4:ään peräkkäin. Ensimmäinen paikka missä 64 on tallennettu tällä hetkellä, koko joukon läpikäynnin jälkeen on selvää, että yksitoista on pienin arvo.
- Korvaa siis 64 luvulla 11. Yhden iteroinnin jälkeen yksitoista , joka sattuu olemaan taulukon pienin arvo, esiintyy yleensä järjestetyn luettelon ensimmäisessä paikassa.
Valintalajittelualgoritmi | Vaihdetaan 1. elementti taulukon minimiin
Toinen passi:
- Toisessa asemassa, jossa on 25, kulje jälleen taulukon loppuosan läpi peräkkäin.
- Matkan jälkeen löysimme sen 12 on taulukon toiseksi pienin arvo ja sen pitäisi näkyä taulukon toisessa paikassa, joten vaihda nämä arvot.
Valintalajittelualgoritmi | vaihtamalla i=1 seuraavaan minimielementtiin
Kolmas passi:
- Nyt kolmannelle sijalle, missä 25 on jälleen läsnä, kulje taulukon loppuosan läpi ja etsi taulukossa oleva kolmanneksi pienin arvo.
- Kulkiessaan, 22 tuli kolmanneksi pienin arvo, ja sen pitäisi näkyä taulukon kolmannella paikalla, joten vaihda 22 jossa elementti on kolmannessa paikassa.
Valintalajittelualgoritmi | vaihtamalla i=2 seuraavaan minimielementtiin
Neljäs passi:
- Samoin neljänteen paikkaa varten kulje taulukon loppuosa ja etsi taulukon neljäs pienin elementti
- Kuten 25 on neljänneksi pienin arvo, joten se sijoittuu neljännelle sijalle.
Valintalajittelualgoritmi | vaihtamalla i=3 seuraavaan minimielementtiin
Viides passi:
- Lopulta taulukon suurin arvo sijoitetaan automaattisesti taulukon viimeiseen kohtaan
- Tuloksena oleva taulukko on lajiteltu taulukko.
Valintalajittelualgoritmi | Pakollinen lajiteltu matriisi
Alla on yllä olevan lähestymistavan toteutus:
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 Python 3 # 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 # Vaihda löydetty minimielementti #:llä ensimmäisellä elementillä A[i], A[min_idx] = A[min_idx], A[i] # Testattava ohjainkoodi yllä olevan tulosteen ('Sorted array) ') i:lle alueella(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>>
Lähtö Aika monimutkaisuus: Valintalajittelun aika monimutkaisuus on PÄÄLLÄ 2 ) koska on kaksi sisäkkäistä silmukkaa: - Yksi silmukka taulukon elementin valitsemiseksi yksitellen = O(N)
- Toinen silmukka, jolla tätä elementtiä verrataan kaikkiin muihin taulukon elementteihin = O(N)
- Siksi kokonaiskompleksisuus = O(N) * O(N) = O(N*N) = O(N2)
Aputila: O(1) on ainoa käytetty lisämuisti väliaikaisille muuttujille vaihdettaessa kahta arvoa Arrayssa. Valintalajittelu ei koskaan tee enempää kuin O(N) vaihtoa ja voi olla hyödyllinen, kun muistin kirjoittaminen on kallista.
merkkijono korvaa kaikki javat
Valintalajittelualgoritmin edut
- Yksinkertainen ja helppo ymmärtää.
- Toimii hyvin pienten tietojoukkojen kanssa.
Valintalajittelualgoritmin haitat
- Valintalajittelun aikamonimutkaisuus on O(n^2) pahimmassa ja keskimääräisessä tapauksessa.
- Ei toimi hyvin suurilla tietojoukoilla.
- Ei säilytä kohteiden suhteellista järjestystä yhtäläisillä avaimilla, mikä tarkoittaa, että se ei ole vakaa.
Usein kysytyt kysymykset valintalajittelusta
Q1. Onko valintalajittelualgoritmi vakaa?
Valintalajittelualgoritmin oletustoteutus on ei vakaa . Se voidaan kuitenkin tehdä vakaaksi. Katso vakaa valintalajittelu yksityiskohtia varten.
Q2. Onko valintalajittelualgoritmi käytössä?
Kyllä, Selection Sort Algorithm on paikallaan oleva algoritmi, koska se ei vaadi ylimääräistä tilaa.