Zadanie2_19

Sortowanie szybkie (quicksort)

(40 min)

Opis zadania

Korzystaj c z przygotowanego interfejsu i algorytmu sortowania szybkiego dopisz procedur sortowania szybkiego. Spróbuj zrealizowa to zadanie rekurencyjnie i iteracyjnie.

Efekt ko cowy

Celem zadania jest nabycie umiej tno ci tworzenia procedur sortowania szybkiego oraz stosowania strategii „dziel i zwyci aj”.

- Aby wykona zadanie niezb dne jest wykorzystanie przygotowanego projektu VB\Programy\Lekcja19\Program2_19\Szybki sort.sln.

Realizacja zadania

W wiczeniu wykorzystasz gotowy interfejs. Dodasz procedur wykorzystuj c szybkie sortowanie i sprawdzisz czy aplikacja działa poprawnie. Podczas realizacji zadania nale y si skoncentrowa na wykorzystaniu strategii „dziel i zwyci aj” w sortowaniu szybkim.

Krok 1 - Otwarcie projektu

!

"

#

$#

% & '(

'

'(

Krok 2 - Dopisanie procedury sortowania

!

Sub Quicksort(ByVal lewy As Integer, ByVal prawy As Integer)

Dim i, j, x, w As Integer

i = lewy

j = prawy

x = tablica((lewy + prawy) \ 2)

Do

While tablica(i) < x

i = i + 1

End While

While x < tablica(j)

j = j - 1

End While

If i <= j Then

w = tablica(i)

tablica(i) = tablica(j)

tablica(j) = w

i = i + 1

j = j - 1

End If

If lewy < j Then

Quicksort(lewy, j)

End If

If i < prawy Then

Quicksort(i, prawy)

End If

Loop Until i > j

End Sub

" #

$

!

Sub szybkie_iteracja()

Dim s, i, j, l, p, x, w As Integer

Dim sl(99) As Integer

Dim sp(99) As Integer

s = 0

sl(0) = 0

sp(0) = 99

Do

l = sl(s)

p = sp(s)

s = s - 1

Do

i = l

j = p

x = tablica((l + p) \ 2)

Do

While tablica(i) < x

i = i + 1

End While

While x < tablica(j)

j = j - 1

End While

If i <= j Then

w = tablica(i)

tablica(i) = tablica(j)

tablica(j) = w

i = i + 1

j = j - 1

End If

Loop Until i > j

If i < p Then

s = s + 1

sl(s) = i

sp(s) = p

End If

p = j

Loop Until l >= p

Loop Until s < 0

End Sub

"

Krok 3 - Testowanie procedur

&

!

Quicksort(0, 99)

'szybkie_iteracja()

" '

(

%

! ) *

#

+, -

.$

) &

%