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