Sortowanie tablic
dr inż. Andrzej Obuchowicz
Algorytmy i struktury danych
Sortowanie tablic
dr inż. Andrzej Obuchowicz
Algorytmy i struktury danych
Drzewo decyzyjne
sortowania
a
b
b
c
a
c
b
c
a
c
a
b
c
c
b
a
b
a
c
b
c
a
c
a
b
a
c
b
Dolne ograniczenie
złożoności
L e m a t : K a ż d e d r z e w o b i n a r n e o w y s o k o ś c i h m a c o n a j w y ż e j 2
h
l i ś c i .
D o w ó d : P r z e z i n d u k c j ę
h = 0 t o m a m y p o j e d y n c z y e l e m e n t c z y l i 2
h
= 2
0
= 1 ;
n i e c h d l a w y s o k o ś c i h d r z e w o b i n a r n e p o s i a d a c o n a j w y ż e j 2
h
l i ś c i
t o
d r z e w o b i n a r n e o w y s o k o ś c i h + 1 m o ż n a p o d z i e l i ć n a k o r z e ń i d w a p o d d r z e w a o
w y s o k o ś c i h o c o n a j w y ż e j 2
h
l i ś c i a c h , m a m y z a t e m 2 * 2
h
= 2
h + 1
l i ś c i .
T w i e r d z e n i e : K a ż d e d r z e w o d e c y z y j n e s o r t u j ą c e n r ó ż n y c h e l e m e n t ó w m a w y s o k o ś ć c o n a j m n i e j
l o g !
n .
D o w ó d : P o n i e w a ż w y n i k i e m p o s o r t o w a n i a m o ż e b y ć k a ż d a z n ! p e r m u t a c j i c i ą g u w e j ś c i o w e g o ,
w i ę c d r z e w o d e c y z y j n e p o s i a d a ć m u s i n ! l i ś c i , s t ą d
2
2
h
n
h
n
!
l o g
!
W n i o s e k : K a ż d y a l g o r y t m s o r t u j ą c y c i ą g n - e l e m e n t o w y z a p o m o c ą p o r ó w n a ń w y k o n u j e c o
n a j m n i e j c n
n c
l o g
(
)
0 p o r ó w n a ń d l a d o s t a t e c z n i e d u ż e g o n .
D o w ó d : Z a u w a ż m y , ż e :
n
n
n n
n
n
n
n
n
n
n
n
n
n
1
1
2
2
2
2
2
4
2
2
!
. . .
/
/
l o g !
l o g
/
/
l o g
/
/
l o g
/
/
Sortowanie przez
wstawianie
9
8
9
1
3
4
2
6
5
1
8
9
1
3
4
2
6
5
3
1
8
9
3
4
2
6
5
4
1
3
8
9
4
2
6
5
2
1
3
4
8
9
2
6
5
6
1
2
3
4
8
9
6
5
5
1
2
3
4
6
8
9
5
1
2
3
4
5
6
8
9
Sortowanie przez
wstawianie c.d.
begin
for i:=2 to n do begin
t[0]:=t[i]; j:=i-1;
while t[0].klucz<t[j].klucz
do begin
t[j+1]:=t[j]; j:=j-1
end;
t[j+1]:=t[0]
end
end;
P
RZESTAWIENIA
P
ORÓWNANIA
M
IN
n-1
2(n-1)
Ś
R
.
(n
2
+n-2)/4
(n
2
+9n-10)/4
M
AX
(n
2
+n)/4 - 1
(n
2
+3n-4)/2
Sortowanie przez wstawianie
połówkowe
begin
for i:=2 to n do begin
t[0]:=t[i]; l:=1; p:=i-1;
while l<=p do begin
m:=(l+p) div 2;
if t[0].klucz<t[m].klucz
then p:=m-1 else l:=m+1
end;
for j:=i-1 downto l do t[j+1]:=t[j];
t[l]:=t[0]
end
end;
P
RZESTAWIENIA
P
ORÓWNANIA
M
IN
n-1
n(logn-loge±0.5)
Ś
R
.
(n
2
+n-2)/4
n(logn-loge±0.5)
M
AX
(n
2
+n)/4 - 1
n(logn-loge±0.5)
Sortowanie przez
wybieranie
8
9
1
3
4
2
6
5
1
9
8
3
4
2
6
5
1
2
8
3
4
9
6
5
1
2
3
8
4
9
6
5
1
2
3
4
8
9
6
5
1
2
3
4
5
9
6
8
1
2
3
4
5
6
9
8
1
2
3
4
5
6
8
9
Sortowanie przez
wybieranie c.d.
begin
for i:=1 to n-1 do begin
k:=i; t[0]:=t[i];
for j:=i+1 to n do
if t[j].klucz<t[0].klucz then begin
k:=j; t[0]:=t[j]
end;
t[k]:=t[i]; t[i]:=t[0]
end
end;
P
RZESTAWIENIA
P
ORÓWNANIA
M
IN
3(n-1)
(n
2
-n)/2
Ś
R
.
?
(n
2
-n)/2
M
AX
trunc(n
2
/4)+ 3(n-1)
(n
2
-n)/2
Sortowanie bąbelkowe
8
9
1
3
4
2
6
5
8
1
3
4
2
6
5
9
1
3
4
2
6
5
8
9
1
3
2
4
5
6
8
9
1
2
3
4
5
6
8
9
1
2
3
4
5
6
8
9
1
2
3
4
5
6
8
9
1
2
3
4
5
6
8
9
Sortowanie bąbelkowe
c.d.
begin
for i:=n-1 downto 1 do
for j:=1 to i do
if t[j].klucz>t[j+1].klucz then begin
t[0]:=t[j]; t[j]:=t[j+1]; t[j+1]:=t[0]
end;
end;
P
RZESTAWIENIA
P
ORÓWNANIA
M
IN
0
(n
2
-n)/2
Ś
R
.
3(n
2
-n)/4
(n
2
-n)/2
M
AX
3(n
2
-n)/2
(n
2
-n)/2
Sortowanie szybkie
(quicksort)
8
9
1
3
4
2
6
5
2
1
3
9
4
8
6
5
1
2
3
5
4
6
8
9
1
2
3
4
5
6
8
9
Sortowani
e
szybkie
c.d.
Procedure podzial(f,l:integer);
i,j,:integer; pomoc: {typ elementu tablicy}
begin
pomoc:=t[(f+l)div 2]; i:=f; j:=l;
repeat
while t[i]<pomoc do i:=i+1;
while t[j]>pomoc do j:=j-1;
if i<=j then begin
t[0]:=t[i]; t[i]:=t[j]; t[j]:=t[0];
i:=i+1; j:=j-1;
end;
until i>j
if f<j then podzial(f,j);
if i<l then podzial(i,l);
end;
Startujemy od
podzial(1,n);
Sortowanie stogowe
(heapsort)
9,8,7,6,3,5,2,4
7
6
8 3
9
2
4
5
7
6
8 3 9 2
4
5
7
4
6 3 5 2
8
9
7
6
8 3 5 2
4
9
7,4,5,8,3,9,2,6
9
4
6 3 5 2
8
7
Sortowanie stogowe c.d.
(1)
Procedure przeczesz(r,b);
var ok:boolean; mc:integer
begin
ok:=false;
while (2*r<=b) and not ok do begin
if 2*r=b then mc:=2*r else
if t[2*r]>t[2*r+1] then mc:=2*r else mc:=2*r+1;
if t[r]<t[mc] then begin
t[0]:=t[r]; t[r]:=t[mc]; t[mc]:=t[0]; r:=mc end;
else ok:=true
end;
end;
Sortowanie stogowe c.d.
(2)
Procedure heapsort;
var i:integer;
begin
for i:=(n div 2) downto 1 do przeczesz(i,n);
for i:=n downto 2 do begin
t[0]:=t[1]; t[1]:=t[i]; t[i]:=t[0];
przeczesz(1,i-1)
end;
end;