selection sort c with examples
O privire aprofundată asupra selecției Sortează în C ++ cu exemple.
După cum sugerează și numele, tehnica de sortare a selecției selectează mai întâi cel mai mic element din matrice și îl schimbă cu primul element din matrice.
Apoi, schimbă al doilea cel mai mic element din matrice cu al doilea element și așa mai departe. Astfel, pentru fiecare trecere, cel mai mic element din matrice este selectat și pus în poziția corectă până când întregul tablou este sortat.
=> Consultați aici ghidul perfect de formare C ++.
Ce veți învăța:
- Introducere
- Algoritm general
- Pseudocod pentru sortare selecție
- Ilustrare
- Exemplu C ++
- Exemplu Java
- Analiza complexității sortării selecției
- Concluzie
- Lectură recomandată
Introducere
Sortarea selecției este o tehnică destul de simplă de sortare, deoarece tehnica implică doar găsirea celui mai mic element din fiecare trecere și plasarea acestuia în poziția corectă.
Sortarea prin selecție funcționează eficient atunci când lista de sortat este de dimensiuni mici, dar performanța sa este afectată grav pe măsură ce lista de sortat crește în dimensiune.
Prin urmare, putem spune că sortarea selecției nu este recomandabilă pentru liste mai mari de date.
Algoritm general
Algoritmul general pentru sortarea selecției este dat mai jos:
ce program deschide un fișier eps
Sortare selecție (A, N)
Pasul 1 : Repetați pașii 2 și 3 pentru K = 1 la N-1
Pasul 2 : Apelați cel mai mic de rutină (A, K, N, POS)
Pasul 3 : Schimbați A (K) cu A (POS)
(Sfârșitul buclei)
Pasul 4 : IEȘIRE
Cel mai mic de rutină (A, K, N, POS)
- Pasul 1 : (initialize) set smallestElem = A (K)
- Pasul 2 : (inițializați) setați POS = K
- Pasul 3 : pentru J = K + 1 la N -1, repetați
if smallestElem> A (J)
set smallestElem = A (J)
set POS = J
(dacă sfârșitul)
(Sfârșitul buclei) - Pasul 4 : returnează POS
Pseudocod pentru sortare selecție
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) Un exemplu pentru a ilustra acest algoritm de sortare a selecției este prezentat mai jos.
Ilustrare
Reprezentarea tabelară pentru această ilustrație este prezentată mai jos:
Listă nesortată Cel mai mic element Listă sortată {18,10,7,20,2} Două {} {18,10,7,20} 7 {Două} {18,10,20} 10 {2.7} {18.20} 18 {2,7,10) {douăzeci} douăzeci {2,7,10,18} {} {2,7,10,18,20}
Din ilustrație, vedem că, la fiecare trecere, cel mai mic element următor este pus în poziția sa corectă în matricea sortată. Din ilustrația de mai sus, vedem că, pentru a sorta o serie de 5 elemente, au fost necesare patru treceri. Acest lucru înseamnă, în general, pentru a sorta o serie de N elemente, avem nevoie de N-1 treceri în total.
Mai jos este implementarea algoritmului de sortare a selecției în C ++.
Exemplu C ++
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<10;i++) { cout< Ieșire:
Lista de intrare a elementelor de sortat
11 5 2 20 42 53 23 34 101 22
Lista sortată a elementelor este
2 5 11 20 22 23 34 42 53 101
Numărul de treceri necesare pentru sortarea matricei: 10
După cum se arată în programul de mai sus, începem sortarea selecției prin compararea primului element din matrice cu toate celelalte elemente din matrice. La sfârșitul acestei comparații, cel mai mic element din matrice este plasat în prima poziție.
În următoarea trecere, utilizând aceeași abordare, următorul cel mai mic element din matrice este plasat în poziția corectă. Acest lucru continuă până la N elemente sau până când întregul tablou este sortat.
Exemplu Java
Apoi, implementăm tehnica de sortare a selecției în limbajul Java.
class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println('
Input list to be sorted...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println('
printing sorted elements...
'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j) Ieșire:
Lista de intrare care trebuie sortată ...
11 5 2 20 42 53 23 34 101 22
imprimarea elementelor sortate ...
2 5 11 20 22 23 34 42 53 101
În exemplul Java de mai sus, aplicăm aceeași logică. Găsim în mod repetat cel mai mic element din matrice și îl plasăm în matricea sortată până când întregul tablou este complet sortat.
Astfel, sortarea selecției este cel mai simplu algoritm de implementat, deoarece trebuie doar să găsim în mod repetat următorul cel mai mic element din matrice și să-l schimbăm cu elementul în poziția sa adecvată.
Analiza complexității sortării selecției
Așa cum se vede în pseudocodul de mai sus pentru sortare de selecție, știm că sortarea de selecție necesită două pentru bucle imbricate între ele pentru a se completa. Unul pentru bucle pasează prin toate elementele din matrice și găsim indexul elementului minim folosind altul pentru buclă care este cuibărit în interiorul buclei externe pentru buclă.
Prin urmare, având în vedere dimensiunea N a matricei de intrare, algoritmul de sortare a selecției are următoarele valori de timp și complexitate.
Complexitatea timpului cel mai prost O (n 2); O (n) swapuri Complexitatea în cel mai bun caz O (n 2); O (n) swapuri Complexitatea timpului mediu O (n 2); O (n) swapuri Complexitatea spațiului O (1)
Complexitatea în timp a lui O ( n Două) se datorează în principal utilizării a două pentru bucle. Rețineți că tehnica de sortare a selecției nu ia niciodată mai mult de swap-uri O (n) și este benefică atunci când operația de scriere a memoriei se dovedește a fi costisitoare.
Concluzie
Sortarea prin selecție este încă o altă simplă tehnică de sortare care poate fi implementată cu ușurință. Sortarea prin selecție funcționează cel mai bine atunci când este cunoscută gama valorilor care urmează a fi sortate. Astfel, în ceea ce privește sortarea structurilor de date folosind sortarea de selecție, putem sorta doar structurile de date care sunt liniare și de dimensiuni finite.
Aceasta înseamnă că putem sorta în mod eficient structuri de date, cum ar fi matrici, folosind sortarea de selecție.
În acest tutorial, am discutat în detaliu sortarea selecției, inclusiv implementarea sortării selecției folosind limbaje C ++ și Java. Logica din spatele sortării de selecție este de a găsi în mod repetat cel mai mic element din listă și de a-l plasa în poziția corectă.
În următorul tutorial, vom învăța în detaliu despre sortarea inserției, despre care se spune că este o tehnică mai eficientă decât celelalte două tehnici pe care le-am discutat până acum, adică sortarea cu bule și sortarea selecției.
=> Verificați aici pentru a vedea A-Z a tutorialelor de formare C ++ aici.
Lectură recomandată
