Sortarea datelor în matrice

În această secțiune va fi considerat un algoritm faimos „“ rapid „“ sortarea, considerat a fi cel mai rapid dintre algoritmi de sortare specializate. Pentru comparație, considerăm, de asemenea, unul dintre algoritmii de sortare care au o eficiență mai scăzută, dar, de asemenea, mai simplu algoritmi - sortare inserare.

sortarea inserturi

Inserția sortare este similar cu procesul de amestecare carduri cu numele. Grefier pune orice nume pe card, și apoi aranjează cărțile în ordine alfabetică prin introducerea cardului în partea de sus a stivei în locul potrivit. Să ne descrie acest proces în exemplul nostru lista cvintuple A = 50, 20, 40, 75, 35 (Figura 1).

Eficiența de calcul a inserțiilor de sortare

Sortarea inserturi necesită un număr fix de treceri. Pe n-1 elemente sunt inserate în pasajele A [1] la A [n-1]. Pe trecere a i-a inserției sunt produse într-o sublista A [0] -A [i] și necesită o medie i / 2 comparații. Numărul total de comparații egal cu

Spre deosebire de alte metode, nu utilizează schimburile inserții de sortare. Complexitatea algoritmului este măsurat și numărul de comparații este egal cu O (n 2). Cel mai bun caz - atunci când lista sursă este deja sortate. Apoi, pe trecere i-lea a inserției este produsă în punctul A [i], iar numărul total de comparații este egal cu n-1, și anume complexitate este O (n). Cel mai rau caz se produce atunci când lista este sortată în ordine descrescătoare. Apoi, fiecare inserție are loc la punctul A [0] i și necesită comparații. Numărul total de comparații este egal cu n (n-1) / 2, și anume complexitate este O (n 2).

„Fast“ sortare

Deci, ne-am uitat la algoritmul de sortare matrice are complexitatea comenzii O (n2). Algoritmi folosind arbori (sortare turneu, sortarea după arborele de căutare), oferă performanțe semnificativ mai bune O (n log2). În ciuda faptului că au nevoie de o copie a matricei într-un copac și înapoi, aceste costuri sunt suportate de o mai mare eficiență de sortare în sine.

Pe scară largă metoda heapsort folosit tratează de asemenea matrice „in situ“ și are o eficiență de O (n log2). Cu toate acestea, „rapid“ de sortare, care a fost inventat K.Hoar, pentru cele mai multe aplicații depășește heapsort și este cel mai rapid cunoscut până acum.

Descrierea de sortare „rapid“

Ca și în cele mai multe algoritmi de sortare, metode de „rapid“ un fel luate din experienta de zi cu zi. Pentru a sorta un teanc mare de cărți alfabetului după nume, pot fi împărțite în două stive mai mici, în ceea ce privește unele litere, cum ar fi numele K. mai mică sau egal cu K, du-te într-o grămadă, iar celălalt - cealaltă.

Apoi, fiecare grămadă din nou împărțită în două. De exemplu, în figura 2 sunt punctele de partiție literele F și R. Procesul de divizare în mai mici și mai mici stivă continuă.

Algoritmul metodei de partiționare de sortare „rapid“ se aplică la determinarea elementului central. Din moment ce nu ne putem permite să arunce un teanc de distracție în jurul mesei ca sortarea alfabetică de cărți, elementele sunt împărțite în grupuri în cadrul șirului. Luați în considerare algoritm „rapid“, de exemplu, sortarea și apoi a discuta detaliile tehnice. Să presupunem că avem o serie de 10 numere întregi:

Faza de scanare

Originalitatea „rapid“ de sortare constă în reacția a doi indici în timpul listei de scanare. indicele scanUp sa mutat în listă, și scanDown - în jos. Noi promovam scanUp înainte element A [scanUp] mai mare decât central în căutarea. În acest moment, scanarea se oprește, și ne pregătim pentru a muta elementul găsit în sublista superioară. Înainte de această mișcare se va întâmpla, vom promova Index scanDown lista și găsi un element mai mic sau egal cu central. Astfel, avem două elemente care nu sunt în sub-liste și pot fi interschimbate.

Acest proces continuă până când scanUp și nu scanDown va scădea unul pentru celălalt (scanUp = 6, scanDown = 5). În acest moment apare în sublista scanDown ale cărui elemente sunt mai mici sau egale cu central. Am ajuns la punctul de divizare cele două liste și a luat act de poziția finală a elementului central. În exemplul nostru am schimbat numerele 600 și 450, 800 și 350, 650 și 400 (vezi Figura 4)..

Apoi, valoarea de schimb a elementului central A, [0] la A [scanDown]:

Ca rezultat, vom vedea două sublistã A [0] - A [5] și A [6] - A [9], în care toate elementele primului sublista un al doilea mai puține elemente, iar ultimul element al primului sublista este elementul său cel mai mare. Astfel, putem presupune că operațiunile sublists după făcut divizat elementul A [5] = 550 (Figura 5). Dacă vom sorta acum sublista fiecărui mod individual, atunci vom obține matrice complet sortat. Rețineți că, de fapt, ambele aceste sublistă sunt aceeași matrice ca și originalul, astfel încât este posibil să se aplice același algoritm. Utilizați același algoritm pentru matrice părți se numește faza recursiv.

faza recursiv

Una și aceeași metodă, cu două prelucrate sublistã: Sl (A [0] - A [4]) și Sh (A [6] - A [9]). Elementul nu ar trebui să fie tratarea unei [5], deoarece este deja în vigoare.

Același algoritm se aplică pentru fiecare sublistă, împărțind sub- liste în bucăți mai mici, până când sublista nu va rămâne un singur element sau până când sublista este gol.

algoritmul sortarerapidă

Acest algoritm recursiv imparte lista A [Low] - O [mare] pe elementul central, care este ales din mijlocul listei

După schimbarea elementului central cu A [scăzut], valorile inițiale sunt date indici scanUp = low + 1 și scanDown = ridicată, indicând începutul și sfârșitul listei, respectiv. Algoritmul controlează acești doi indici. În primul rând scanUp se mișcă în sus pe listă până când aceasta depășește scanDown sau până când un element mai mare decât centrul.

După poziționarea indicelui scanUp scanDown se deplasează în jos lista până când întâlnește un element mai mic sau egal cu central.

Element de schimb încetează atunci când scanDown devine mai mică decât scanUp. În acest moment indică începutul scanDown sublistă stâng, care cuprinde mai mică sau egală cu elementele centrale. Indexul scanDown devine centrală. Marcați elementul central al A [scăzut]:

Pentru tratamentul sub-liste folosind recursivitate. După detectarea punctului de divizare noi numim recursiv parametrii sortarerapidă cu un nivel scazut, la mijlocul-1 și la mijlocul + 1, de mare. condiția de oprire se produce atunci când sublista este mai mică decât două elemente, ca un Singleton sau un array gol nu trebuie să se organizeze.

Complexitatea de calcul a sortarea „rapid“

Analiza de ansamblu a eficienței de sortare „rapid“ este destul de dificil. Ar fi mai bine să arate complexitatea de calcul, numărarea numărului de comparații pentru anumite ipoteze ideale. Să presupunem că n - puterea a doua, n = 2 k (k = log2 n), iar elementul central este situat exact în mijlocul fiecărei liste și îl împarte în două sublistã lungimi aproximativ egale.

Prima scanare este efectuată n-1 comparații. Acest lucru creează două dimensiune sublistã de n / 2. În următoarea fază de prelucrare a fiecărui sublistã necesită aproximativ n / 2 comparații. Numărul total de comparații în această fază este egal cu 2 (n / 2) = n. Următoarea fază patru sublists sunt procesate, care necesită 4 (n / 4) comparații etc. La sfârșitul procesului de partiție este terminată după k trece atunci când sublists rezultate conțin un singur element. Numărul total de comparații egal cu aproximativ

Pentru o listă a complexității computaționale totală a formei de „rapid“ de sortare este O (n log2 n). Cazul ideal care ne-am uitat la, de fapt, are loc atunci când o matrice este deja sortate în ordine crescătoare. Apoi, elementul central cade exact în mijlocul fiecărei sub-listă.

În cazul în care matricea este sortată în ordine descrescătoare, apoi să treacă mai întâi elementul central se găsește în mijlocul listei și este schimbat cu fiecare element atât primul și al doilea sublista. Lista rezultată sortată aproape algoritm are o complexitate de ordinul O (n log2 n).

În cel mai rău caz, pentru o sortare „rapid“ va fi cel în care elementul central al tuturor timpurilor intră în Singleton sublistă, și toate celelalte elemente rămân în al doilea sublista. Acest lucru se întâmplă atunci când centrul este întotdeauna cel mai mic element. Să considerăm o secvență de 3, 8, 1, 5, 9.

La prima trecere se face n comparații și mai sublistã conține n-1 elemente. Pe următoarea trecere, acest sublistã necesită n-1 și oferă comparații sublistã de n 2-elemente, etc. Numărul total de comparații este:

Cel mai rău caz complexitatea este O (n 2), adică nu mai bine decât sortarea inserturi și alegere. Cu toate acestea, acest caz este patologică și este puțin probabil în practică. În general, performanța medie a „rapid“ evaluare de calitate mai mare decât cea considerată de noi tot felul.

Algoritmul sortarerapidă este selectat ca baza unor instrumente de sortare cele mai versatile. Dacă nu puteți veni la termeni cu performanță cel mai rău caz, utilizați heapsort - mai algoritm stabil, a cărei complexitate este O (n log2 n) și depinde numai de mărimea listei.

matrice Compararea algoritmii de sortare

În general, sortarerapidă este cel mai rapid algoritm. Datorită eficienței sale egală cu O (n log2), este net superioară oricărui algoritm de comandă O (n 2). Judecând după rezultatele testelor enumerate în tabelul de mai jos, de asemenea, este mai rapid decât oricare din ordinea de sortare a O (n log2 n), am discutat în ultimul număr. Vă rugăm să rețineți că eficacitatea de sortare „rapid“ este O (n log2 n), chiar și în cazuri extreme. Dar sortarea prin arborele de căutare în aceste cazuri devine O (n 2) complex, format ca copacul este degenerată.

Sortare după copac

Fig.8 Compararea ordinea O sortare (n log2)

compararea de soiuri

Acest program realizează o comparație a algoritmilor de sortare, datele prezentate în figurile 7 și 8. Aici vom prezenta doar structura de bază a programului. Momentul TickCount realizată folosind o funcție care returnează numărul de 1/60 fracțiuni de secundă, care au trecut de la începutul programului.