Atlases kārtošana ir vienkāršs un efektīvs kārtošanas algoritms, kas darbojas, atkārtoti atlasot mazāko (vai lielāko) elementu no nešķirotās saraksta daļas un pārvietojot to uz sakārtoto saraksta daļu.
Algoritms atkārtoti atlasa mazāko (vai lielāko) elementu no saraksta nešķirotās daļas un apmaina to ar nešķirotās daļas pirmo elementu. Šo procesu atkārto atlikušajai nešķirotajai daļai, līdz viss saraksts ir sakārtots.
Kā darbojas atlases kārtošanas algoritms?
Ieteicamās prakses izvēle Kārtot Izmēģiniet to!Apskatīsim šādu masīvu kā piemēru: arr[] = {64, 25, 12, 22, 11}
Pirmā piespēle:
- Pirmajā pozīcijā sakārtotajā masīvā viss masīvs tiek secīgi šķērsots no indeksa 0 līdz 4. Pirmā pozīcija, kur 64 tiek saglabāts pašlaik, pēc visa masīva šķērsošanas ir skaidrs, ka vienpadsmit ir zemākā vērtība.
- Tādējādi aizstājiet 64 ar 11. Pēc vienas atkārtojuma vienpadsmit , kas ir vismazākā vērtība masīvā, mēdz parādīties sakārtotā saraksta pirmajā pozīcijā.
Atlases kārtošanas algoritms | 1. elementa maiņa ar minimālo masīvā
Otrā caurlaide:
- Otrajā pozīcijā, kur ir 25, atkal secīgi šķērsojiet pārējo masīvu.
- Pēc šķērsošanas mēs to atradām 12 ir otrā mazākā vērtība masīvā, un tai vajadzētu parādīties masīva otrajā vietā, tādējādi apmainiet šīs vērtības.
Atlases kārtošanas algoritms | nomainot i=1 ar nākamo minimālo elementu
Trešā caurlaide:
- Tagad par trešo vietu, kur 25 ir klāt vēlreiz, šķērsojiet pārējo masīvu un atrodiet trešo mazāko vērtību, kas atrodas masīvā.
- Ceļojot, 22 iznāca kā trešā mazākā vērtība, un tai vajadzētu parādīties masīva trešajā vietā, tādējādi nomainiet 22 ar elementu trešajā pozīcijā.
Atlases kārtošanas algoritms | nomainot i=2 ar nākamo minimālo elementu
Ceturtā piespēle:
- Tāpat ceturtajā pozīcijā šķērsojiet pārējo masīvu un atrodiet ceturto mazāko elementu masīvā
- Kā 25 ir 4. zemākā vērtība, tāpēc tā ieņems ceturto pozīciju.
Atlases kārtošanas algoritms | nomainot i=3 ar nākamo minimālo elementu
Piektā caurlaide:
- Beidzot lielākā masīvā esošā vērtība automātiski tiek novietota masīva pēdējā pozīcijā
- Iegūtais masīvs ir sakārtots masīvs.
Atlases kārtošanas algoritms | Nepieciešams sakārtots masīvs
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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 # Apmainiet atrasto minimālo elementu ar # pirmo elementu A[i], A[min_idx] = A[min_idx], A[i] # Pārbaudāmais draivera kods virs drukas ('Sorted array ') i diapazonā(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>>
Izvade Laika sarežģītība: Atlases kārtošanas laika sarežģītība ir O(N 2 ) jo ir divas ligzdotas cilpas: - Viena cilpa, lai atlasītu masīva elementu pa vienam = O(N)
- Vēl viena cilpa, lai salīdzinātu šo elementu ar visiem citiem masīva elementiem = O(N)
- Tāpēc kopējā sarežģītība = O(N) * O(N) = O(N*N) = O(N2)
Palīgtelpa: O(1) kā vienīgā izmantotā papildu atmiņa ir paredzēta pagaidu mainīgajiem, vienlaikus apmainot divas vērtības masīvā. Atlases kārtošana nekad neveic vairāk par O(N) mijmaiņas darījumiem, un tā var būt noderīga, ja ierakstīšana atmiņā ir dārga.
ja vēl paziņojumi java
Atlases kārtošanas algoritma priekšrocības
- Vienkārši un viegli saprotami.
- Labi darbojas ar nelielām datu kopām.
Atlases kārtošanas algoritma trūkumi
- Atlases šķirošanas laika sarežģītība ir O(n^2) sliktākajā un vidējā gadījumā.
- Nedarbojas labi lielās datu kopās.
- Nesaglabā relatīvo vienumu secību ar vienādiem taustiņiem, kas nozīmē, ka tā nav stabila.
Bieži uzdotie jautājumi par atlases kārtošanu
Q1. Vai atlases kārtošanas algoritms ir stabils?
Atlases kārtošanas algoritma noklusējuma ieviešana ir nav stabils . Tomēr to var padarīt stabilu. Lūdzu, skatiet stabila atlases kārtošana sīkākai informācijai.
Q2. Vai atlases kārtošanas algoritms ir ieviests?
Jā, atlases kārtošanas algoritms ir iebūvēts algoritms, jo tam nav nepieciešama papildu vieta.