Sortert utvalg - Sorted array
| Sortert utvalg | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Array | ||||||||||||||||||||
| Oppfunnet | 1945 | ||||||||||||||||||||
| Oppfunnet av | John von Neumann | ||||||||||||||||||||
| Tidskompleksitet i stor O-notasjon | |||||||||||||||||||||
| |||||||||||||||||||||
En sortert matrise er en matardatastruktur der hvert element er sortert i numerisk, alfabetisk eller annen rekkefølge og plassert på like adresser i dataminnet. Det brukes vanligvis innen informatikk for å implementere statiske oppslagstabeller for å inneholde flere verdier som har samme datatype . Sortering av en matrise er nyttig for å organisere data i bestilt form og gjenopprette dem raskt.
Metoder
Det er mange kjente metoder som en matrise kan sorteres, som inkluderer, men er ikke begrenset til: Utvalg sortere , boble sortere , innsetting sort , flettesortering , Quicksort , Heapsort , og Counting sort . Disse sorteringsteknikkene har forskjellige algoritmer knyttet til seg, og det er derfor forskjellige fordeler ved å bruke hver metode.
Oversikt
Sorterte matriser er den mest plasseffektive datastrukturen med den beste referanselokaliteten for sekvensielt lagrede data.
Elementer i en sortert matrise blir funnet ved hjelp av et binært søk , i O (log n ); dermed er sorterte matriser egnet for tilfeller der man trenger å kunne slå opp elementer raskt, f.eks. som et sett eller en multisett datastruktur . Denne kompleksiteten for oppslag er den samme som for selvbalanserende binære søketrær .
I noen datastrukturer brukes en rekke strukturer. I slike tilfeller kan de samme sorteringsmetodene brukes til å sortere strukturene etter en hvilken som helst nøkkel som et strukturelement; for eksempel sortering av poster av studenter etter rulletall eller navn eller karakterer.
Hvis man bruker en sortert dynamisk matrise , er det mulig å sette inn og slette elementer. Innsetting og sletting av elementer i en sortert matrise utføres ved O ( n ), på grunn av behovet for å forskyve alle elementene som følger elementet som skal settes inn eller slettes; til sammenligning setter inn og sletter et selvbalanserende binært søketre ved O (log n ). I tilfelle der elementer slettes eller settes inn på slutten, kan en sortert dynamisk matrise gjøre dette på amortisert O (1) tid mens et selvbalanserende binært søketre alltid opererer ved O (log n ).
Elementer i en sortert matrise kan slås opp av indeksen ( tilfeldig tilgang ) ved O (1) tid, en operasjon som tar O (log n ) eller O ( n ) tid for mer komplekse datastrukturer.
Historie
John von Neumann skrev det første array-sorteringsprogrammet ( merge sort ) i 1945, da den første lagrede programdatamaskinen fortsatt ble bygget.
Anvendelser av sorterte matriser
Kommersiell databehandling
Offentlige organisasjoner, private selskaper og mange nettbaserte applikasjoner må håndtere store mengder data. Dataene må ofte være tilgjengelige flere ganger. Å holde dataene i et sortert format muliggjør rask og enkel henting.
I diskret matematikk
Sorterte matriser kan brukes til å implementere Dijkstras algoritme eller Prims algoritme . Også algoritmer som Kruskals algoritme for å finne minimale spennende trær.
I prioritert planlegging
På operativsystemnivå venter mange prosesser om gangen, men de kan bare håndtere en prosess av gangen. Derfor er prioriteringer knyttet til hver prosess. Deretter sendes prosessene til CPU i henhold til høyeste prioritet ved å bruke sortert utvalg av prosess-IDer. Her ble prosesser sortert avhengig av prioriteringene deres, og deretter blir CPU tildelt dem. Prosessen med høyest prioritet inntar førsteplass i sortert matrise. Derfor prioriteres systemprosesser planlegging er gjort.
I korteste jobb-første planlegging
Dette er det spesielle tilfellet med prioritetsplanlegging. Her blir prosesser sortert i henhold til prosessens burst-tid. Prosessen som krever kortest tid, blir tildelt CPU først. Derfor blir prosesser sendt til CPU i henhold til deres burst-tid.
| Prosess | Bursttid |
|---|---|
| P1 | 3 |
| P2 | 4 |
| P3 | 1 |
| P4 | 8 |
| P5 | 6 |
