Student: Bartosz Janaszek (1M10) [e-mail]

Prowadzący: J.Olszyna

Podstawy programowania (PRM) – projekt

Specyfikacja strukturalna (techniczna)

Temat: Posortowanie tablicy liczb algorytmem Quicksort

Algorytm rozwiązania zadania:

Do posortowania tablicy został zastosowany słynny algorytm Quicksort. Procedura quicksort działa w następujący sposób: najpierw funkcja wybiera spośród elementów tablicy element środkowy. Jest to podział (pivot) według, którego funkcje dalej rozdziela elementy tablicy. Poprze kolejne wywołania rekurencyjne procedura rozdziela elementy tablicy według podziału.

Algorytm:

Procedura quicksort

Dane wejściowe (tablica)

{

Określenie początku i końca tablicy ( l i p)

Wybieranie „podziału(pivot)”

Pętla do while:

{

Porównywanie elementu „pivot” z kolejnymi elementami tablicy(od jej początku, a potem od końca). Porównywanie trwa dopóki procedura nie odnajdzie elementu mniejszego(lub równego) i większego(lub równego).

Następnie funkcja zamienia wartości znalezionych elementów tablicy

}

Jeżeli cała tablica nie jest jeszcze posortowana procedura wywołuje się ponownie.

Struktury danych:

Program będzie się posługiwał tablicą n-elementową wprowadzoną przez użytkownika.

Podział na funkcje:

• void quicksort(int a[], int l, int r)

  • funkcja algorytmu

• int main(void)

  • wprowadzanie n-elementów tablicy

    • jeżeli dane nie zostaną wprowadzone program zakończy się

    • procedura quicksort uruchmi się w przypadku, gdy użytkownik wprowadzi n lub mniej elementów (wprowadzanie kończy wpisanie wszystkich elementów, bądź wpisanie „00”)

  • po uzyskaniu danych uruchami się procedura quicksort

  • wypiszanie posortowanych elementów

Literatura

Wróblewski P. Algorytmy - struktury danych i techniki programowania.