Articles

Hvad er sortering?


Bedste svar

I datalogi er en sorteringsalgoritme er en algoritme, der placerer elementer på en liste i en bestemt rækkefølge. De mest anvendte ordrer er numerisk rækkefølge og leksikografisk rækkefølge. Effektiv sortering er vigtig for at optimere effektiviteten af ​​andre algoritmer (som søge- og flettealgoritmer), som kræver, at inputdata er i sorterede lister. Sortering er også ofte nyttigt til kanonisering af data og til produktion af menneskeligt læsbart output. Mere formelt skal output fra enhver sorteringsalgoritme opfylde to betingelser:

  • Outputtet er i ikke-faldende rækkefølge (hvert element er ikke mindre end det forrige element i henhold til den ønskede samlede rækkefølge);
  • Outputtet er en permutation (en ombestilling, men bevarer alle de originale elementer) af inputet.

Yderligere lagres inputdataene ofte i en matrix, som tillader tilfældig adgang snarere end en liste, som kun tillader sekventiel adgang; selvom mange algoritmer kan anvendes på begge typer data efter passende modifikationer.

Sorteringsalgoritmer kaldes ofte et ord efterfulgt af ordet “sorter” og bruges grammatisk på engelsk som navneordssætninger, for eksempel i sætningen “det er ineffektivt at bruge indsættelsessortering på store lister”, udtrykket indsættelsessort refererer til sorteringsalgoritmen til indsættelsessortering.

Svar

Sortering af en milliard objekter er bestemt inden for rækkevidde, hvis du kan gemme dem i hukommelsen. Du har brug for som O (n log n) sammenlignet, ikke? Hvis du ikke kan, kan du sortere, hvad der passer i hukommelsen på din computer (eller computere, hvis du har et distribueret system) og flette sortering af resultaterne. På et tidspunkt i 1990erne havde en modificeret fusionssorter verdenshastighedsrekord og en super lineær pr. CPU-hastighed op.

Noget andet, du gør, er dog, når N bliver stor (eller faktisk når noget bliver langsomt for rimelige input), ser du nærmere på, hvad du virkelig har brug for.

Hvorfor har du brug for at sortere objekterne? Hvis du bare leder efter duplikater, er der langt hurtigere måder! Hvis du vil behandle bunden (eller toppen) 5\%, er der O (n) algoritmer, der kan partitioneres baseret på post sorteringsposition!

Når ting bliver langsomme, ser du på, hvad der gør, og inden du finder ud af, om det er den hurtigste algoritme, skal du gøre hvad det er, skal du finde ud af, om det faktisk er den rigtige ting at gøre overhovedet! (undtagelse: hvis den hurtigere “uanset” er en allerede debugget tynd, kan du bare smække ind, så kan det godt være bedre at gøre det … ligesom hvis du finder dig At teste, om en matrix indeholder et element mange mange gange, kan det være enklere at erstatte arrayet med et sæt og se, om det nu er hurtigt nok, at du ikke er ligeglad med, at hvis du foretog yderligere seks timers forskning, kunne du fjerne halvdelen af kontrollerne eller hvad som helst).

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *