Hvordan sorterer du en bøtte?

2024 Forfatter: Lynn Donovan | [email protected]. Sist endret: 2024-01-18 08:27

Bøttesortering fungerer som følger:

1. Sett opp en rekke med opprinnelig tomme " bøtter ".
2. Scatter: Gå over den originale matrisen, og legg hvert objekt i sitt bøtte .
3. Sortere hver ikke-tom bøtte .
4. Samle: Besøk bøtter i rekkefølge og sett alle elementene tilbake i den opprinnelige matrisen.

Dessuten, hva er bøttesortering med eksempel?

Du vil også finne arbeid eksempler av bøtte sortering i C, C++, Java og Python. Bøttesortering er en sortering teknikk som sorterer elementene ved først å dele elementene i flere grupper kalt bøtter . Elementene blir først spredt inn i bøtter deretter elementene i bøtter er sortert.

Videre, hvor brukes bøttesortering? Bøtte sortering er hovedsakelig nyttig når input er jevnt fordelt over et område. Tenk for eksempel på følgende problem. Sortere et stort sett med flytende kommatall som er i området fra 0,0 til 1,0 og er jevnt fordelt over området.

Når du tar dette i betraktning, hvordan finner du antall bøtter i en bøttesortering?

Hvis bøtter har lengde 2^k, hver bøtte har størrelse en, og bøtte sortering utarter til telling sortere . Så du vil ha hver bøtte størrelse til å være mer enn 1. Hvis vi har n bøtter , og msbits(x, k) returnerer 2^k verdier, deretter hver bøtte størrelsen er 2^k/n.

Hva er tidskompleksiteten til bøttesortering?

Den gjennomsnittlige tidskompleksitet til Bøttesortering er O(n + k). Det verste tidskompleksitet er O(n²). Verdensrommet kompleksitet til Bøttesortering er O(n+k).