Matrice sortată - Sorted array
| Matricea sortată | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tip | Matrice | ||||||||||||||||||||
| Inventat | 1945 | ||||||||||||||||||||
| Inventat de | John von Neumann | ||||||||||||||||||||
| Complexitatea timpului în notația O. mare | |||||||||||||||||||||
| |||||||||||||||||||||
O matrice sortată este o structură de date matrice în care fiecare element este sortat în ordine numerică, alfabetică sau în altă ordine și plasat la adrese la distanță egală în memoria computerului. Este de obicei utilizat în informatică pentru a implementa tabele de căutare statice pentru a conține mai multe valori care au același tip de date . Sortarea unei matrice este utilă în organizarea datelor în formă ordonată și recuperarea lor rapidă.
Metode
Există multe metode bine cunoscute prin care se poate sorta o matrice, care includ, dar nu se limitează la: Sortare selecție , sortare cu bule , sortare prin inserție , sortare Merge , Quicksort , Heapsort și sortare Counting . Aceste tehnici de sortare au algoritmi diferiți asociați și, prin urmare, există diferite avantaje în utilizarea fiecărei metode.
Prezentare generală
Tablourile sortate sunt structura de date cea mai eficientă din punct de vedere spațial, cu cea mai bună localitate de referință pentru datele stocate secvențial.
Elementele dintr-o matrice sortată se găsesc folosind o căutare binară , în O (jurnal n ); astfel, matricile sortate sunt potrivite pentru cazurile în care trebuie să puteți căuta rapid elemente, de exemplu ca o structură de date set sau multiset . Această complexitate pentru căutări este aceeași ca și pentru arborii de căutare binari auto-echilibrați .
În unele structuri de date, se utilizează o serie de structuri. În astfel de cazuri, aceleași metode de sortare pot fi utilizate pentru a sorta structurile în funcție de o anumită cheie ca element de structură; de exemplu, sortarea înregistrărilor studenților în funcție de numere sau nume sau note.
Dacă se folosește o matrice dinamică sortată , atunci este posibilă inserarea și ștergerea elementelor. Inserarea și ștergerea elementelor într-o matrice sortată se execută la O ( n ), datorită necesității de a schimba toate elementele care urmează elementului care urmează să fie inserat sau șters; în comparație, un arbore de căutare binar auto-echilibrat inserează și șterge la O (jurnal n ). În cazul în care elementele sunt șterse sau inserate la sfârșit, o matrice dinamică sortată poate face acest lucru în timp amortizat O (1) în timp ce un arbore de căutare binar auto-echilibrat funcționează întotdeauna la O (jurnal n ).
Elementele dintr-o matrice sortată pot fi căutate prin indexul lor ( acces aleatoriu ) la momentul O (1), o operație luând timp O (jurnal n ) sau O ( n ) timp pentru structuri de date mai complexe.
Istorie
John von Neumann a scris primul program de sortare matrice ( sort sort ) în 1945, când încă se construia primul computer cu program stocat .
Aplicații ale matricelor sortate
Calcul comercial
Organizațiile guvernamentale, companiile private și multe aplicații web trebuie să se ocupe de cantități uriașe de date. Datele vor trebui adesea accesate de mai multe ori. Păstrarea datelor într-un format sortat permite regăsirea rapidă și ușoară.
În matematică discretă
Tablourile sortate pot fi utilizate pentru a implementa algoritmul lui Dijkstra sau algoritmul lui Prim . De asemenea, algoritmi precum algoritmul lui Kruskal pentru găsirea copacilor minimi.
În programarea prioritară
La nivel de sistem de operare , multe procese sunt în așteptare la un moment dat, dar poate gestiona un singur proces la o singură instanță în timp. Prin urmare, prioritățile sunt asociate fiecărui proces. Apoi procesele sunt trimise către CPU în funcție de cea mai mare prioritate utilizând o matrice sortată de ID-uri de proces. Aici, procesele au fost sortate în funcție de prioritățile lor și apoi CPU le este alocat. Procesul cu cea mai mare prioritate ocupă prima poziție în matricea sortată. Prin urmare, se face planificarea proceselor de sistem prioritare.
În programarea cea mai scurtă pentru primul loc de muncă
Acesta este cazul special al planificării prioritare. Aici, procesele sunt sortate în funcție de timpul de explozie al proceselor. Procesul care necesită cel mai scurt timp va fi alocat mai întâi CPU. Prin urmare, procesele sunt trimise către CPU în funcție de timpul lor de rafală.
| Proces | Timp de spargere |
|---|---|
| P1 | 3 |
| P2 | 4 |
| P3 | 1 |
| P4 | 8 |
| P5 | 6 |
