Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Aktualna kategoria: Nauka » Informatyka » Liceum - lekcje

123456789101112131415161718...2122
Lekcja: "Algorytmy sortujące - sortowanie kubełkowe, sortowanie grzebieniowe"

Sortowanie kubełkowe (bucket sort)

Jest to jeden z najbardziej popularnych algorytmów sortowania. Został wynaleziony w 1956 r. przez E.J. Issaca i R.C. Singletona.
Algorytm działa w czasie liniowym O(n).
Algorytm najlepiej się sprawdza dla zbiorów zawierających dużą liczbę elementów, liczb całkowitych jednak o małym zakresie ich wartości.
W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n2).
Zazwyczaj przyjmuje się, że sortowane liczby należą do przedziału od 0 do 1. Jeśli tak nie jest, to można podzielić każdą z nich, przez największą możliwą (jeśli znany jest przedział) lub wyznaczoną. Algorytm ma klasę czasowej złożoności obliczeniowej O(m+n), gdzie m oznacza ilość możliwych wartości, które mogą przyjmować elementy zbioru, a n to ilość sortowanych elementów. Jeśli m jest małe w porównaniu z n (sortujemy dużo elementów o małym zakresie wartości), to na czas sortowania będzie miała wpływ głównie ilość elementów n i klasa złożoności uprości się do postaci O(n).
Dla osiągnięcia optymalnej złożoności liczba kubełków powinna być rzędu liczby elementów.

<< Poprzednia plansza   Następna plansza >>
Pobierz lekcję

Udostępnij link do tej lekcji innym uczniom:




Zgłoś uwagę do lekcji:




Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie