wyklad11 drukuj, WIMiIP IS, Algorytmy i Struktóry Danych, Wykłady
[ Pobierz całość w formacie PDF ]
Sortowaniekubełkowe.
W algorytmie
sortowaniekubełkowe
zakładamy, »e dana jest
n
-elementowa tablica wej±ciowa
A
, której elementy s¡ liczbami
rzeczywistymi z przedziału
[
0
,
1
)
.
Sortowanie kubełkowe polega na podziale przedziału
[
0
,
1
)
na
n
podprzedziałów jednakowych rozmiarów, tzw.
kubełków
, a
nast¦pnie „rozrzuceniu” liczb wej±ciowych do kubełków, do których
nale»¡. Aby otrzyma¢ ci¡g wynikowy, sortujemy najpierw liczby w
ka»dym kubełku, a nast¦pnie wypisujemy je, przegl¡daj¡c po kolei
kubełki.
Zauwa»my, »e je±li liczby wej±ciowe s¡ rozło»one jednostajnie w
przedziale
[
1
,
0
)
, to mo»emy oczekiwa¢, »e w ka»dym z kubełków
b¦dzie ich niewiele.
W procedurze BUCKET-SORT korzystamy z pomocniczej tablicy
list (kubełków)
B
[
0
..
n
−
1
]
.
BUCKET-SORT(
A
,
n
)
1.
begin
2.
for
i
:=
1
to
n
do
3. wstaw
A
[
i
]
na list¦
B
[
b
nA
[
i
]
c
]
;
4.
for
i
:=
0
to
n
−
1
do
5. posortuj list¦
B
[
i
]
przez wstawianie;
6. poł¡cz listy
B
[
0
]
,
B
[
1
]
,...,
B
[
n
−
1
]
z zachowaniem kolejno±ci;
7.
end;
Przykład.
W celu sprawdzenia poprawno±ci sortowania kubełkowego
rozwa»my dwa elementy
A
[
i
]
i
A
[
j
]
.
Bez straty ogólno±ci mo»emy zało»y¢, »e
A
[
i
]
A
[
j
]
.
Poniewa»
b
nA
[
i
]
cb
nA
[
j
]
c
, element
A
[
i
]
zostanie umieszczony
albo w tym samym kubełku co
A
[
j
]
, albo w kubełku o ni»szym
indeksie.
Je±li
A
[
i
]
i
A
[
j
]
s¡ w tym samym kubełku, to p¦tla
for
w wierszach
4-5 zapewni ustawienie ich we wła±ciwej kolejno±ci.
Je±li
A
[
i
]
i
A
[
j
]
s¡ w ró»nych kubełkach, to wiersz 6 zapewni
ustawienie ich we wła±ciwej kolejno±ci.
Tak wi¦c algorytm działa poprawnie.
Tablicy wej±ciowa:
A
= [
0
.
78
,
0
.
17
,
0
.
39
,
0
.
26
,
0
.
72
,
0
.
94
,
0
.
21
,
0
.
12
,
0
.
23
,
0
.
68
]
0
.
26
"
0
.
17 0
.
23 0
.
78
" " "
0
.
12 0
.
21 0
.
39 0
.
68 0
.
72 0
.
94
B
=
[ /
" " "
/ /
" "
/
"
]
Kubełek
B
[
i
]
zawiera liczby z przedziału
[
i
/
10
,
(
i
+
1
)
/
10
)
.
/ oznacza pust¡ list¦. Ci¡g wynikowy powstaje przez poł¡czenie
list w kolejno±ci
B
[
0
]
,
B
[
1
]
,...,
B
[
9
]
.
Tablica
B
[
0
..
9
]
posortowanych list (kubełków) po zako«czeniu p¦tli
for
w wierszach 4-5:
Załó»my, »e dane wej±ciowe zostały wybrane losowo z przedziału
[
0
,
1
)
, zgodnie z rozkładem jednostajnym.
Oznacza to, »e dla ka»dego
i
2{
0
,...,
n
−
1
}
i ka»dego
j
2{
1
,...,
n
}
element
A
[
j
]
wpada do kubełka
B
[
i
]
z jednakowym
prawdopodobie«stwem równym 1
/
n
. Zakładamy ponadto, »e liczby
zostały wybrane niezale»nie.
Zmienna losowa
Czasdziałania
Zauwa»my, »e ł¡czny czas działania wszystkich instrukcji procedury
BUCKET-SORT, oprócz wiersza 5, wynosi
(
n
)
.
Niech
n
i
b¦dzie zmienn¡ losow¡ oznaczaj¡c¡ liczb¦ elementów
umieszczonych w kubełku
B
[
i
]
. Sortowanie przez wstawianie
n
i
liczb zajmuje czas
(
n
2
i
)
. St¡d ł¡czny czas działania
BUCKET-SORT wynosi
T
(
n
) = (
n
) +
n
−
X
(
n
2
i
)
.
(
1
je±li
A
[
j
]wpadadokubełka
B
[
i
]
0
je±li
A
[
j
]niewpadadokubełka
B
[
i
]
i
=
0
X
ij
=
Korzystaj¡c z własno±ci warto±ci oczekiwanej (liniowo±¢ i
monotoniczno±¢), mamy:
przyjmuje warto±¢ 1 z prawdopodobie«stwem 1
/
n
.
Dla
j
6
=
k
zmienne
X
ij
i
X
ik
s¡ niezale»ne.
E
(
T
(
n
)) = (
n
) +
n
−
X
(
E
(
n
2
i
))
.
i
=
0
Poka»emy, »e
E
(
n
2
i
) =
2
−
1
/
n
.
Mamy
n
i
=
n
X
X
ij
,
j
=
1
0
@
n
X
1
A
2
n
X
X
2
ij
+
X
1
j
n
X
E
(
n
2
i
) =
n
X
n
+
X
1
j
n
X
n
2
=
n
·
1
n
+
n
(
n
−
1
)
1
n
2
=
2
−
1
n
.
n
2
i
=
X
ij
=
X
ij
X
ik
,
j
=
1
1
k
n
k
6
=
j
j
=
1
j
=
1
1
k
n
k
6
=
j
n
X
E
(
X
2
ij
) +
X
1
j
n
X
Wstawiaj¡c do wzoru na
E
(
T
(
n
))
mamy:
E
(
n
2
i
) =
E
(
X
ij
X
ik
)
,
n
−
X
j
=
1
1
k
n
k
6
=
j
E
(
T
(
n
)) = (
n
) +
(
E
(
n
2
i
)) = (
n
) +
n
(
2
−
1
/
n
)
i
=
0
E
(
X
2
ij
) =
1
·
1
1
−
1
n
=
1
n
.
Poniewa» dla
k
6
=
j
zmienne
X
ij
i
X
ik
s¡ niezale»ne, zatem
n
+
0
·
E
(
T
(
n
)) = (
n
)
.
Tak wi¦c algorytm sortowania kubełkowego działa w oczekiwanym
czasie
(
n
)
dla danych wej±ciowych rozmiaru
n
.
E
(
X
ij
X
ik
) =
E
(
X
ij
)
E
(
X
ik
) =
1
n
=
1
n
2
.
n
1
1
·
1
[ Pobierz całość w formacie PDF ]