BAL 2011 cwicz4 id 78937 Nieznany (2)

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:
BAL 2011 cwicz6 id 78938 Nieznany (2)
BAL 2011 cwicz 3 id 78934 Nieznany (2)
BAL 2011 cwicz 5 id 78935 Nieznany (2)
BAL 2011 cwicz6 id 78938 Nieznany (2)
Egzamin 2011 algebra id 151848 Nieznany
AMB ME 2011 wyklad01 id 58945 Nieznany (2)
4OS 2011 w5 id 39385 Nieznany
marzec 2011 wybrane id 281154 Nieznany
19 07 2011 ucho(1)id 18427 Nieznany
chemia proz maj 2011 cke id 112 Nieznany
AMB ME 2011 wyklad04 id 58946 Nieznany (2)
4OS 2011 w1 id 39381 Nieznany (2)
4OS 2011 w8 id 39387 Nieznany
GPW biuletyn 2011 01 id 194038 Nieznany
egz sem 2 analiza 2011 12 id 15 Nieznany
kalendarium UJ 2011 2012 id 230 Nieznany

więcej podobnych podstron