Cum se folosește Sortarea selecției

Sortarea prin selecție este o tehnică de sortare care selectează un element din listă și apoi schimbă locul acestuia cu altul. Selectează cel mai mare element și apoi îl schimbă cu un element din cel mai înalt indice al listei.

Algoritmul face acest lucru în mod repetat până când lista este sortată. Dacă nu sunteți foarte sigur cum funcționează sortarea selecției, ați ajuns la locul potrivit. Vă vom explica mai detaliat mai jos, împreună cu vă vom arăta un exemplu.

Selecție Sortare: O privire mai atentă

Să presupunem că aveți lista: [39, 82, 2, 51, 30, 42, 7]. Pentru a sorta lista folosind sortarea de selecție, ar trebui să găsiți mai întâi cel mai mare număr din ea.

Cu lista dată, acest număr este 82. Schimbați 82 cu numărul din cel mai mare indice (adică 7).

După prima trecere, noua listă va fi: [39, 7, 2, 51, 30, 42, 82]. De fiecare dată când algoritmul trece prin întreaga listă, se numește „trecere”.

Observați că lista menține o sublistă sortată și o sublistă nesortată în timpul procesului de sortare.

Legate de: Ce este notația Big-O?

Lista originală începe cu o listă sortată de zero elemente și o listă nesortată a tuturor articolelor. Apoi, după prima trecere, are o listă sortată care are doar numărul 82.

La a doua trecere, cel mai mare număr din sublista nesortată va fi 51. Acest număr va fi schimbat cu 42 pentru a da noua listă de ordine de mai jos:

[39, 7, 2, 42, 30, 51, 82].

Procesul se repetă până când se sortează întreaga listă. Figura de mai jos rezumă întregul proces:

Numerele în negru aldin arată cea mai mare valoare din listă la acel moment. Cei în verde arată sublista sortată.

Analiza algoritmului

Pentru a obține complexitatea (folosind notația Big-O) a acestui algoritm, urmați mai jos:

La prima trecere, se fac comparații (n-1). La a doua trecere, (n-2). La a treia trecere, (n-3) și așa mai departe până la (n-1) a trece, care face o singură comparație.

Rezumând comparațiile, după cum urmează, oferă:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

Prin urmare, sortarea selecției este O (n²).

Implementarea codului

Codul afișează funcțiile pe care le puteți utiliza pentru efectuarea sortării de selecție folosind Python și Java.

Piton:

def selectionSort (lista mea):
pentru x în interval (len (lista mea) - 1, 0, -1):
max_idx = 0
pentru pozn în interval (1, x + 1):
dacă lista mea [posn]> lista mea [max_idx]:
max_idx = posn
temp = lista mea [x]
lista mea [x] = lista mea [max_idx]
lista mea [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
pentru (int x = 0; x { 
int index = x; 
pentru (int y = x + 1; y if (my_array [y] index = y; // găsiți cel mai mic indice 
} 
} 
int temp = matricea_mea [index]; // temp este o stocare temporară
my_array [index] = my_array [x]; 
my_array [x] = temp; 
}}

Trecând de la Sortare la selecție la Merge Sortare

Așa cum a arătat analiza algoritmului de mai sus, algoritmul de sortare a selecției este O (n²). Are o complexitate exponențială și, prin urmare, este ineficient pentru seturi de date foarte mari.

Un algoritm mult mai bun de utilizat ar fi sortarea fuzionării cu o complexitate de O (nlogn). Și acum știți cum funcționează sortarea de selecție, în lista de studiu pentru algoritmi de sortare ar trebui să fie sortarea de îmbinare.

Despre autor