prykens

Sortowanie kubełkowe co to:

Bucket sort - algorytm sortowania który jest stosowany w specyficznych sytuacjach których liczby są rozłożone równomiernie.

Nazwa pochodzi od tego iż dane wrzucamy do kubełków, które sa już z definicji posortowane.

Osobą która pierwszy raz użyła ten typ sortowania jest: E. J. Issac i R. C. Singleton, zrobili to w 1956.

Zasada działania dzielenia kubełkowego:

1. Podziel zadany przedział liczb na k podprzedziałów (kubełków) o równej długości:

Zanim zaczniesz cokolwiek robić musisz utworzyć strukturę pomocniczą. Przykładowo, wiemy, że nasze liczby mieszczą się w przedziale 0-25, ten zakres dzielimy na mniejsze, równe części, które w informatyce są nazywane kubełkami.

Przykład: 0-5, 6-10, 11-20, 21-25.

Przypisz liczby z sortowanej tablicy do odpowiednich kubełków:

Przechodzimy do naszej nieposortowanej listy liczb, każda z naszych liczb musi trafić do odpowiedniego kubełka

Przykład: 2, 3 , 12,25, 4 - kubełek 1: 2,3,4, kubełek 3: 12, kubełek 4: 25.

3. Sortuj liczby w niepustych kubełkach.

Teraz zajmujemy się losowaniem kubełkiem z osobna, gdyż w każdym kubełku znajduje się nie wielka ilość liczb, sortowanie ich jest bardzo szybkie. Używamy do tego innego, prostego algorytmu sortowania np. sortowania przez wstawianie. Jeśli kubełek jest pusty, jest on pomijany.

4. Wypisz po kolei zawartość niepustych kubełków.

Zazwyczaj przyjmuje się, że sortowane liczby należą do przedziału od 0 do 1 => 0.12, 0.15, 0.34 itd.

Jeśli tak nie jest, to można podzielić każdą z nich przez największą możliwą liczbę => polega to na niczym innym jak przeskalowania, mając mamy liczbę 500 w zbiorze do 1000, musimy ją podzielić, przez co wyjdzie nam 0.5.
Dzięki temu działaniu nasza liczba pasuje do standardowego wzoru algorytmu który operuje na ułamkach.

Należy tu jednak zwrócić uwagę, że wyznaczanie największej możliwej liczby w tablicy m-elementowej ma złożoność obliczeniową O(m). => oznacza to, że komputer szukając największą liczbę z przedziału, musi rzucić okiem na każdy element zbioru jeden raz.

np. w przedziałe 0 - 1 000 000 komputer musi wykonać milion operacji, by znaleźć największą.

Czym jest O(m)?

Jest to informatyczny zapis, który można zapisać w taki sposób: "Czas szukania rośnie w lini prostej wraz z ilością danych"

Przykład schematu blokowego:

Przykład kodu napisanego w c++

Uwaga! Poniższy kod to (counting sort) jest to uproszczona wersja sortowania kubełkowego, jednakże działają na takiej samej zasadzie.

#include <iostream>

#include <iomanip>

#include <cstdlib>

#include <time.h>

using namespace std;

int main()

{

const int WMIN = -99;

const int WMAX = 99;

const int N = 80;

int d[N],lw[WMAX - WMIN + 1],i,j;

cout << " Sortowanie kubelkowe \n"

"----------------------\n"

srand((unsigned)time(NULL));

for(i = 0; i < N; i++)

d[i] = WMIN + rand() %

(WMAX - WMIN + 1);

cout << "Przed sortowaniem:\n\n";

for(i = 0; i < N; i++)

cout << setw(4) << d[i];

cout << endl;

for(i = WMIN; i <= WMAX; i++)

lw[i - WMIN] = 0;

for(i = 0; i < N; i++)

lw[d[i] - WMIN]++;

j = 0;

for(i = WMIN; i <= WMAX; i++)

while(lw[i - WMIN]--)

d[j++] = i;

cout << "\nPo sortowaniu:\n\n";

for(i = 0; i < N; i++)

cout << setw(4) << d[i];

cout << endl << endl;

system("pause");

return 0;

}

Jego działanie:

Roznica miedzy counting sort

sa podobne poniewaz najpierw porzodkuja liczby a potem pokazuje

counting sort

ile jest 2, iel 3 ile 4

bocket sort wklada liczby do pudelka i robi przedzaly

Rozbicie kodu:

Zaczynamy od wyzerowania licznika czyli lw, bedzie to nam wyswietlac liczbe poszczegolnych wartosci, kazdy element otrzymuje wartosc zero.

for(i = WMIN; i <= WMAX; i++)

lw[i - WMIN] = 0;

petla for przechodzi przez wszystkie elementy tablicy czyli d, dla kazdfej liczby wziweksza odpowiedni licznik w tablicy lw o 1, robi to po to, aby komputert wiedzial ile razy liczba zostala wyswietlona
for(i = 0; i < N; i++)

lw[d[i] - WMIN]++;

petla for przechodzi przez wszystkie mozliwe wartosci od najmniejszej do najwiekszej, petla while sprawdza ile razy dana liczba wystapila (na podstawie licznika lw), i przepisuje w tablicy wynikowej czyli d dokladnei tyel razy, przez to ze dane sa zapisywane od najmniejszej do najwiekszej sa one ulozone w porzadku rosnacym

j = 0; for(i = WMIN; i <= WMAX; i++)

while(lw[i - WMIN]--)

d[j++] = i;

Wyświetleniue zawartości zbioru po sortowaniu
cout << "\nPo sortowaniu:\n\n";

for(i = 0; i < N; i++)

cout << setw(4) << d[i];

phyton

Tworzenie kubelkow - w przeciwienstwie do poprzedniego kodu gdzie tworzylismy pojedyczne liczniki (liczby), tutaj tworzymy tablice dynamicznych list [] to kubełek

bucket = []

for i in range(len(array)):

bucket.append([])

Rozdzielanie danych do kubelkow - ta linijka odpowaida za przepisanie liczby do odpowiedniego kubelka, a nie liczy ilosc wystapien jak w c++, wrzucamy liczbe w dany kubelek (append.j)

for j in array:

index_b = int(10 * j)

bucket[index_b].append(j)

Ten kawalek odpowiada za losowanie wnetrza kubelka

for i in range(len(array)):

bucket[i] = sorted(bucket[i])

w ostatnim punkcie przechodzimy po kolei przez wszystkie posortwane kubelki i przepisujemy ich zawartosc do glownej tablicy czyli array

k = 0

for i in range(len(array)):

for j in range(len(bucket[i])):

array[k] = bucket[i][j]

k += 1

Plusy i minusy sortowania kubełkowego

Plusy:

Szybkość działania - przez to, że algorytm działa w systemie liniowym potrafi on w niesamowicie dużym tępie wykonywać sortowania, gdy ma do tego warunki czyli gdy dane są równomiernie rozłożone. W takim środowisku jest on dużo szybszy niż np sortowanie bąbelkowe.
Łatwość podziału pracy - Przez to, że każdy kubełek jest niezależny, ten system idealnie nadaje się dla nowoczesnych procesorów, gdyż kubełek 1 może być przypisany dla 1 rdzenia, kubełek 2 dla drugiego itd.
Minusy:
1. Duże zużycie pamięci Ram
2. Duża wrażliwość na strukturę danych - Algorytm zakłada, że liczby są w miarę równo ułożone pomiędzy kubełkami, ale jeśli tak nie jest i np 90% liczb trafia do kubełka o numerze 1 to algorytm drastycznie zwalnia i staje się bezużyteczny.
3. Wymagana wiedzy o danych - Żeby ten algorytm miał sens, muisz wiedzieć w jakim przedziale są liczby np 0-100, klasyczne sortowania np. Quicksort nie pytają o zakres.

źródła: https://eduinf.waw.pl/inf/alg/003_sort/0020.php, https://pl.wikipedia.org/wiki/Sortowanie_kube%C5%82kowe , materiały Klaudi Janiuch