Sortowanie kubełkowe w Pythonie

powrót

Algorytm został opisany w tym miejscu.

Sortowanie kubełkowe (ang. bucket sort) jest algorytmem, który rozdziela elementy do kubełków, a następnie każdy kubełek sortuje osobno używając dowolnego algorytmu sortowania. Algorytm ten jest szczególnie efektywny, gdy dane wejściowe są równomiernie rozłożone.

Najważniejsze cechy algorytmu:

• stabilność algorytmu zależy od algorytmu sortującego kubełki,
• złożoność algorytmu jest rzędu $$O(n)$$ dla danych równomiernie rozłożonych,
• algorytm nie sortuje w miejscu — potrzebuje dodatkową listę na kubełki.

Zadanie

Posortuj niemalejąco zbiór liczb całkowitych algorytmem sortowania kubełkowego.

Wejście

W pierwszym wierszu jedna liczba n określająca wielkość zbioru (nie większa niż milion). W drugim wierszu n liczb naturalnych równorozłożonych w przedziale [0..2*10⁹).

Wyjście

Posortowany zbiór wypisany w jednym wierszu.

Przykład

Wejście:

10
300000000 2399 900000000 1899999999 500000001 1400200000 1799999999 123456678 1999999999 1210000000

Wyjście:

2399 123456678 300000000 500000001 900000000 1210000000 1400200000 1799999999 1899999999 1999999999 

#*****************www.algorytm.edu.pl****************
n = int(input()) # wielkość zbioru do posortowania
p = 2000000000 // n # zakres jednego kubełka
# przedziały dla kolejnych kubełkow:
# [0, p), [p, 2p), [2p, 3p), ..., [(n-1)p, n*p)


# wczytanie liczb i wrzucenie ich do odpowiednich kubełków
lista = list(map(int, input().split()))
kubelki = [list() for i in range(len(lista))]

for i in lista:
    # wrzucam liczbę do odpowiedniego kubełka
    kubelki[i // p].append(i)

#sortowanie elementów w poszczególnych kubełkach
for i in range(len(kubelki)):
    # sortujemy tylko, jesli kubełek ma co najmniej dwie liczby
    if len(kubelki[i]) > 1:
        kubelki[i].sort()

# wypisanie posortowanych liczb
for kubelek in kubelki:
    for i in kubelek:
        print(i, end = ' ')