Inserția sortare - studopediya
inserțiile de sortare (Insertion sort) - algoritmul de sortare simplu, în care se adaugă un alt element întotdeauna la sfârșitul listei și apoi se mută la partea de sus a listei, atâta timp cât acesta este mai mic decât elementul precedent.
Astfel, în mod formal, acesta este un loc potrivit pentru a insera (de exemplu, sortarea cărți în bibliotecă). Acest algoritm va avea următoarea secvență de pași.
1. Etapa de inițializare. element de matrice este deja sortate în funcție de ascendent și servește ca o listă inițială.
2. Etapa iterație. Pentru toate elementele ulterioare ale doilea la n -1, elementul următor i este comparat cu toate elementele anterioare de la 0 la (i-1), în timp ce elementul curent i este mai mic sau egal cu cel anterior. După aceasta se găsește poziția de a introduce sau se va ajunge la partea de sus a listei. După aceea, elementul este inserat în poziția găsită.
Să presupunem că avem următoarea matrice:
Analiza complexității computaționale arată că, în orice caz, este necesar să se producă (n-1) pass. În fiecare dintre aceste pasaje, în cel mai bun caz, atunci când matrice este sortată în ordine crescătoare, este necesară o comparație. În acest caz, permutarea nu este, iar costul de calcul va fi
.
În cel mai rău caz, atunci când matricea este sortat în ordine descrescătoare pentru fiecare (n-1) i trece comparații necesare cu elemente anterioare. Complexitatea de calcul este proporțională. În medie, fiecare trecere va necesita mai puțin de jumătate. Prin urmare, în medie. Complexitatea de calcul este încă proporțională.
O diagramă bloc a unui inserturi algoritmului de sortare are forma:
Punerea în aplicare a acestui algoritm în C ++ după cum urmează:
void InsertSort (T * A, const int n)
în timp ce (j> 0 Temp Algoritmul sortarerapidă (Sortare rapidă). dezvoltate engleză Informatică Charles Hoare, și este în prezent cel mai rapid dintre toate celelalte tipuri de soiuri. Ea se bazează pe o interacțiune unică între cei doi indici ScanUp și ScanDown. și poate fi descrisă după cum urmează: 1. Etapa de inițializare. Intrarea algoritmului și transmisă unui element de matrice de coduri inițiale (reduse) și sfârșitul (ridicat). După aceea este indicele, care este situat în mijlocul listei. Apoi, primul și elementul de mijloc sunt interschimbate. astfel, elementul de mijloc va fi localizat la poziția zero și este comparată cu toate celelalte elemente cu indici (scăzut +1) la ridicat. Indexul ScanUp se execută întreaga listă și sa oprit, în cazul în care se constată mai multe elemente decât mijloc (prima ScanUp = scăzut +1). Lista indicele ScanDown va rula de la capăt la început, până când întâlnește elementul mai mic sau egal cu elementul de mijloc. Inițial, aceasta este stabilită la sfârșitul listei. 2. Etapa iterație. Pentru toate elementele de la poziția ScanUp până la sfârșit, ScanUp a crescut cu 1, până când găsește un element care este mai mare decât elementul median sau până când se ajunge la sfârșitul listei. Astfel, ScanUp va indica un element care nu este în sublistă său, adică toate elementele ScanUp să fie mai mică sau egală cu mijloc. Indexul Ulterior ScanDown a scăzut cu 1, până când se găsește un element mai mic sau egal cu mijloc sau până în partea de sus a listei este atins (ScanDown 3. Ieșire Etapa. pas iterare este realizată atât timp cât ScanDown este mai mică decât ScanUp. Aceasta înseamnă că întreaga listă este împărțit în două părți, cu valori mai mici sau egale cu elementul din mijloc și cu valori mai mari membru medial. Ei au în comun indicele poziția ScanDown. După acest element de mijloc în poziția zero și elementul cu noduri index ScanDown. 4. Etapa recursivitate. Etapele 1-3 se repetă pentru sublistă stângă cu elemente de la mic la ScanDown -1 și la dreapta - de la ScanDown +1 la înălțime, atâta timp cât lista nu rămâne gol sau o Singleton. Să matrice originală are forma: