Algoritmi de sortare în C

Un cifru este o secvenţă de operaţii după care atribuie prioritate la un ordin de elemente într-o ordine stabilită în conformitate cu un raport. Aceste linii vor fi expuse cele mai frecvente (cu probe un'approccio foarte orientat) şi fiecare va fi comentat cu privire la meritele şi defectele.
Pentru simplitate în exemplele vor fi întotdeauna folosit ca un set de numere naturale, precum şi relaţia de ordine ca şi cea a majorităţii, algoritmii sunt încă expuse universal valabile, nete de o lucrare scurtă de adaptare a codului.

Selecţia sortare

Pentru a comanda un număr stabiliţi un înainte şi intuiţia pot fi scanate ca de multe ori ca transportatorul toate elementele sale, cu fiecare pas căutare pentru valoarea minimă şi adăugaţi-l la secvenţa de ordonate, identificate iniţial cu un transportator al doilea;

 Exemplu: {5,1,3,8,2}







 Pasul # 1 -> {1, X, X, X, X}







 Pasul # 2 -> {1,2, X, X, X}







 Pasul # 3 -> {1,2,3, X, X}







 Pasul # 4 -> {1,2,3,5, X}







 Pasul # 5 -> {1,2,3,5,8}

(X este marcat cu o amplasare a operatorului de transport noi nu a fost încă scris)

Din punct de vedere al spaţiului în memorie, acest algoritm aplicat în acest fel este extrem de dezavantajos deoarece setul initial este copiat la altul. Un truc simplu este de a înlocui operaţie de copiere corective cu schimbul de valoarea minimă a constatat doar primul element care nu este parte din subsetul de numere deja comandate.

 Exemplu: {5,1,3,8,2}







 Pasul # 1 -> {1,5,3,8,2}







 Pasul # 2 -> {1,2,3,8,5}







 Pasul # 2 -> {1,2,3,8,5}







 Pasul # 3 -> {1,2,3,5,8}

Cifru se modifică după selecţie, care urmează o punere în aplicare posibilă:

 sel_sort (int * v, int size)







 {



   



 int i = 0, temp = 0, y = 0, j = 0;



   



 pentru (i = 0, i = j -)



   



 {

  

      



 {



         



 temp = v [j];



         



 y = j;



      



 }

  

   



 de swap (v, i, y) / / Swap poziţiile în vectorul v iey



   



 }







 }

Bucla dubla este amplasat ghici că numărul de comparatii efectuate de acest algoritm este de un pătrat decât numărul de elemente.
Acest lucru înseamnă că o serie de comparaţii sunt făcute la comandă de mărime egală cu pătratul numărului de elemente din colecţie.
Reţineţi că, în cazurile normale, este numărul de comparatii să cântărească eficienţa şi operaţiunilor rămase, cele mai multe misiuni, au un cost neglijabil în comparaţie cu comparaţia.
Când trebuie să ordinea înregistrările de dimensiuni considerabile, numărul de schimburi are o influenţă decisivă asupra performanţei. În acest al doilea caz, după selecţie se dovedeste a fi o soluţie excelentă şi optimă, deoarece fiecare element este mutat cel mult o dată.

După selecţie este, de asemenea, un algoritm stabil.
Un algoritm stabil păstrează efectul de comenzile anterioare, în cazul structurilor de date sunt tratate în mai multe chei, cum ar fi Nume complet:

 1.

 



 Charles verde







 2.

 



 Andrea Rossi







 3.

 



 Mario Rossi







 4.

 



 Luciano Bianchi

Am obligarea câmpurile pentru prenume:

 1.

 



 Andrea Rossi







 2.

 



 Charles verde







 3.

 



 Mario Rossi







 4.

 



 Luciano Bianchi

Acum ne comandă pe numele de familie, un algoritm mult mai stabilă va păstra ordinea de prioritate iniţiale ale tale, sau, în caz de egalitate între tastele de pe care se comanda, este poziţia de prim ordin pentru a determina locaţia finală.

 1.

 



 Luciano Bianchi







 2.

 



 Andrea Rossi







 3.

 



 Mario Rossi







 4.

 



 Charles verde

Un algoritm stabil se va asigura că, în acest caz precede întotdeauna Mario Rossi, Andrea Rossi. Unul nu are un comportament stabil, nu este previzibil, astfel încât aceasta ar putea fi inversat poziţiile 2 şi 3.

Sortare de selecţie este, de asemenea, pe site-ul.
Un algoritm este declarat pe loc (sau chiar în loc), în cazul în care nu ia un spaţiu de memorie suplimentar decât baza de date originală, sau este o sumă mică constantă.

• <<
• 1
• 2
• 3
• 4
• 5
• >>