Articles

Ce este sortarea?


Cel mai bun răspuns

În informatică, un algoritm de sortare este un algoritm care pune elementele unei liste într-o anumită ordine. Cele mai frecvent utilizate ordine sunt ordinea numerică și ordinea lexicografică. Sortarea eficientă este importantă pentru optimizarea eficienței altor algoritmi (cum ar fi algoritmii de căutare și îmbinare) care necesită ca datele de intrare să fie în liste sortate. Sortarea este, de asemenea, adesea utilă pentru canonicalizarea datelor și pentru producerea de rezultate citibile de către om. Mai formal, ieșirea oricărui algoritm de sortare trebuie să îndeplinească două condiții:

  • Ieșirea este în ordine nedescrescătoare (fiecare element nu este mai mic decât elementul anterior conform ordinii totale dorite);
  • Ieșirea este o permutare (o reordonare, dar care reține toate elementele originale) a intrării.

În plus, datele de intrare sunt adesea stocate într-o matrice, care permite accesul aleator, mai degrabă decât o listă, care permite doar accesul secvențial; deși mulți algoritmi pot fi aplicați oricărui tip de date după o modificare adecvată.

Algoritmii de sortare sunt adesea menționați ca un cuvânt urmat de cuvântul „sortare”, iar gramaticale sunt folosiți în engleză ca fraze substantive, pentru exemplu din propoziție, „este ineficient să se utilizeze sortarea inserției pe liste mari”, expresia sortarea inserției se referă la algoritmul de sortare a sortării inserției.

Răspuns

Sortarea unui miliard de obiecte este cu siguranță la îndemână dacă le poți păstra în memorie. Ai nevoie de O (n log n) comparat, nu? Dacă nu puteți, puteți sorta ceea ce se potrivește în memorie pe computerul dvs. (sau computerele dacă aveți un sistem distribuit) și combinați rezultatele. La un moment dat în anii 90, un sortare de îmbinare modificată avea recordul de viteză mondial și un super liniar pe CPU accelerați.

Altceva faceți, totuși, este când N devine mare (sau, de fapt, ori de câte ori ceva devine lent pentru intrări rezonabile), aruncați o privire mai atentă asupra a ceea ce aveți cu adevărat nevoie.

De ce trebuie să sortați obiectele? Dacă sunteți doar în căutarea de duplicate, există modalități mult mai rapide! Dacă doriți să procesați 5\% (sau sus) 5\% există algoritmi O (n) care pot partiționa în funcție de post sortează poziția!

Când lucrurile devin lente, te uiți la ceea ce face și, înainte de a-ți da seama dacă acesta este cel mai rapid algoritm, faci orice ești, îți dai seama dacă acesta este de fapt ceea ce trebuie făcut Deloc! (Excepție: dacă „orice” mai rapid este un subțire deja depanat pe care îl poți pălmui, atunci poate fi mai bine să faci asta … ca și cum te găsești Testarea dacă o matrice conține un element de multe ori, poate fi mai simplu să înlocuim matricea cu un set și să vedem dacă acum este suficient de rapid încât să nu îți pese că dacă ai face încă șase ore de cercetare ai putea elimina jumătate din verificările sau orice altceva).

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *