BAL - ćwiczenia nr 4
23 listopada 2011
Zadanie
Skonstruuj algorytm wybierania (selekcji) z tablicy T (N ) elementu o najm-
niejszej wartości liczbowej.
Algorithm 1 A4.1: Algorytm selekcji
DANE WEJŚCIOWE: T (N )
min ← 1
powtarzaj od j = 2 do N
jeśli T
j
< T
min
min ← j
zakończ iterację
zakończ iterację
WYJŚCIE: T
min
Iteracyjne algorytmy sortowania
Algorithm 2 A4.2: Sortowanie przez selekcję
DANE WEJŚCIOWE: T (N )
powtarzaj od i = 1 do i = N − 1
min ← i
powtarzaj od j = i + 1 do N
jeśli T
j
< T
min
min ← j
zakończ iterację
zamień(T
i
, T
min
)
zakończ iterację
WYJŚCIE: T (N )
Dla każdego i -tego elementu wektora T wśród elementów T
i
, T
i+1
, . . . , T
N
zna-
jdujemy ten o najmniejszej wartości (T
min
), a następnie zamieniamy go miejs-
cami z elementem T
i
. W ten sposób w pierwszej iteracji znajdziemy element
tablicy T o najmniejszej wartości, i wstawimy go na pierwszą pozycję w tablicy,
w drugiej iteracji - najmniejszy z pozostałych, i wstawimy go na drugie miejsce
w tablicy, itd.
1
Algorithm 3 A4.3: Sortowanie “bąbelkowe”
DANE WEJŚCIOWE: T (N )
powtarzaj od i = 1 do N − 1
powtarzaj od j = 1 do N − i
jeśli T
j
> T
j+1
zamień(T
j
, T
j+1
)
zakończ iterację
zakończ iterację
WYJŚCIE: T (N )
W wyniku porównywania sąsiadyjacych elementów tablicy T po pierwszej it-
eracji na końcu tablicy znajdzie się element o największej wartości. Po drugiej it-
eracji - element o największej wartości spośród pozostałych osiągnie przedostat-
nie miejsce w tablicy, itd.
Algorithm 4 A4.4: Sortowanie przez wstawianie
DANE WEJŚCIOWE: T (N )
powtarzaj od i = 2 do N
pom ← T
i
j ← i
dopóki (j > 1 oraz T
j−1
> pom) powtarzaj
T
j
← T
j−1
j ← j − 1
zakończ iterację
T
j
← pom
zakończ iterację
WYJŚCIE: T (N )
Rekurencyjne algorytmy sortowania
Algorithm 5 A4.5: Rekurencyjne sortowanie “szybkie”
procedura Sort_Quick(T, L, P )
jeśli L < P
S ← L
powtarzaj od i = L + 1 do P
jeśli T
i
< T
L
S ← S + 1
zamień(T
S
, T
i
)
zakończ iterację
zamień(T
S
, T
L
)
Sort_Quick(T, L, S − 1)
Sort_Quick(T, S + 1, P )
zakończ procedurę
2