Cunoaște Intuit, curs, matrice de sortare

sarcina de sortare

Acest curs este dedicat pur algoritmice problemă prin care se dispune de date.

Necesitatea de a sorta orice magnitudine are loc în programare foarte des. De exemplu, datele de intrare sunt furnizate „mixt“, iar programul este mai convenabil să se ocupe de o secvență ordonată. Există situații în care o sortare preliminară a datelor poate reduce o parte substanțială a algoritmului uneori, și în timp ce se execută - în zeci de ori.

Cu toate acestea, opusul este adevărat. Nu contează cât de bine și eficient indiferent de algoritmul ales. dar, în cazul în care utilizează sub-sarcini ca „rele“, sortarea toate lucrările cu privire la optimizarea acestuia este inutil. implementate necorespunzător sortarea datelor de intrare poate reduce semnificativ eficiența algoritmului în ansamblu.

Metodele prin care se dispune sunt împărțite în interne (matrici de prelucrare) și exterior (care se ocupă cu fișiere numai) 1 Pentru mai multe informații despre diferitele algoritmi de comanda, a se vedea cartea lui Donald Knuth lui „Arta calculator de programare“, volumul 3, „sortarea și căutarea.“

Acest curs va fi dedicat numai pentru sortarea internă. Caracteristica lor importantă este faptul că acești algoritmi nu necesită memorie suplimentară: toate lucrările pentru a fluidiza produs în cadrul aceleiași matrice.

sortare simplu

Prin metodele simple de sortare interne includ complexitatea care este proporțională cu pătratul dimensiunii datelor de intrare. Cu alte cuvinte, matrice de sortare. compus din componente N. Astfel de algoritmi vor fi efectuate * N 2 de acțiune, în cazul în care C - o constantă.

Numărul de acțiuni necesare pentru a comanda o secvență de date, desigur, nu depinde numai de lungimea secvenței, dar, de asemenea, pe structura sa. De exemplu, în cazul în care intrarea este deja comandat secvență (ce program. Comprehensibile nu știu), numărul de operațiuni va fi mult mai mică decât în ​​cazul de intrare mixte.

De obicei, complexitatea algoritmilor sunt numărate separat pentru numărul de comparații și numărul de circulație a datelor în depozit (transferuri), deoarece aceste operații să ia momente diferite. Cu toate acestea, valorile exacte sunt rareori în măsură să găsească, așa că pentru algoritmii de evaluare sunt limitate la termenul „proporțional“, care nu ia în considerare valorile specifice ale constantelor în formula finală. Eficiența generală a algoritmului este de obicei evaluată „în medie“: media aritmetică a complexității algoritmului „cel mai bun“ și „cel mai rău“, adică (Eff_best + Eff_worst) / 2.

Sortare prin simpla introducere

Cel mai simplu mod de a sorta 2 Numele algoritmii le urmăm Knut. care vine în minte - această ordine de date pe măsură ce devin disponibile. În acest caz, atunci când intră fiecare valoare nouă se poate baza pe faptul că toate elementele anterioare formează deja o secvență de sortate.

1. Primul element de a scrie „fără ezitare“.
2. Până la sfârșitul secvenței datelor de intrare, pentru fiecare componentă nouă a acestuia pentru a efectua următoarele etape:

- începând de la sfârșitul unei secvențe ordonate existente, toate elementele sale, care sunt mai mari decât elementul nou introdus pentru a muta 1 pas înapoi;

- înregistra un nou element pentru un loc.

În același timp, desigur, puteți citi toate elementele de intrare în același timp, să le scrie într-o matrice, și apoi „imagina“, că fiecare element succesivă a fost introdus doar asta. Pe de natura și structura algoritmului nu este afectată.

Punerea în aplicare a algoritmului PrVst