Er spandsorteringsalgoritmen på plads?

2024 Forfatter: Lynn Donovan | [email protected]. Sidst ændret: 2023-12-15 23:45

Nej, det er ikke en in- placere sortering algoritme . Hele ideen er det input sorterer sig selv, når de flyttes til spande . I det værste af de gode tilfælde (sekventielle værdier, men ingen gentagelse) er den nødvendige ekstra plads lige så stor som den oprindelige matrix.

Hvilke sorteringsalgoritmer er på denne måde på plads?

Som et andet eksempel omarrangerer mange sorteringsalgoritmer arrays i sorteret rækkefølge på stedet, herunder: boble sortering , kam sortering, udvælgelsessortering, indsættelsessortering , heapsort og Shell sortering. Disse algoritmer kræver kun nogle få pointere, så deres rumkompleksitet er O(log n). Quicksort opererer på plads på de data, der skal sorteres.

Efterfølgende er spørgsmålet, hvordan fungerer en spandsorteringsalgoritme? Spand sortering , eller bin sortering , er en sorteringsalgoritme at arbejder ved at fordele elementerne i et array i et antal spande . Hver spand er da sorteret individuelt, enten ved hjælp af en anden sorteringsalgoritme , eller ved rekursivt at anvende spandsorteringsalgoritme . Opsæt et array med oprindeligt tomme " spande ".

I overensstemmelse hermed, hvordan implementerer du en bucket-sorteringsalgoritme?

1. Antag, at input-arrayet er: Opret et array med størrelse 10.
2. Indsæt elementer i spandene fra arrayet. Elementerne indsættes i henhold til spandens rækkevidde.
3. Elementerne i hver spand sorteres ved hjælp af en hvilken som helst af de stabile sorteringsalgoritmer.
4. Elementerne fra hver spand er samlet.

Hvor bruges spandsortering?

Spand sortering er primært nyttig, når input er ensartet fordelt over et område. Overvej f.eks. følgende problem. Sortere et stort sæt flydende kommatal, som ligger i området fra 0,0 til 1,0 og er ensartet fordelt over området.