Sprawozdanie – Jerzy Jurczak nr albumu 13578

Do wykonania były następujące zadania:

1. Zakoduj w Scilabie trzy wybrane algorytmy sortowania.

2. Przeprowadź analizę ich wydajności w przypadku gdy:

a) wejściowa tablica jest uporządkowana rosnąco,

b) wejściowa tablica jest uporządkowana malejąco,

c) wejściowa tablica jest częściowo uporządkowana,

d) wejściowa tablica jest losowa.

Pracować należało na próbach dla 100,500 i 1000 wartości.

Wyniki doświadczeń zbierz w postaci tabelarycznej, a także na wykresach w

skalach liniowo-liniowej i logarytmiczno-logarytmicznej.

Pierwszy krokiem było wczytanie tablic z poszczególnymi wartościami. Tablice A reprezentowały tablice 100-elementowe, tablice B 500-elementowe i tablice C 1000-elementowe. Indeksy przy nazwach tablic oznaczały poszczególnie 1 – posortowane rosnąco, 2 – posortowane malejąco, 3 – wartości losowe, 4 – wartości częściowo uporządkowane. Wykorzystane było tutaj polecenia typu:

A1=1:100 (dla tablicy 100 elementów posortowanej rosnąco)

A2= 100:-1:100 (dla tablicy 100 elementowej posortowanej malejąco)

A3= int(rand(100,1)*100) (dla talbicy 100 elementowej z losowymi wartościami(

W następnej kolejności należało utworzyć funkcje z algorytmami sortowania, z których będziemy korzystać. W tym wypadku były to: sortowanie bąbelkowe, sortowanie przez scalanie oraz sortowanie szybkie. Funkcja odpowiadająca za częściowe sortowanie powstała z modyfikacji algorytmu sortowania przez scalanie (warunek if L>=P-5 then).

Mając przygotowane funkcje i obiekty przechodziliśmy do badania czasu trwania poszczególnych algorytmów na poszczególnych rozmiarach tablic.

Korzystaliśmy w tym przypadku z polecenia typu:

timer() ; quick_sort (A4,1,100);t1=timer() (czas sortowania szybkiego dla tablicy 100 elementowej częściowo uporządkowanej)

Uzyskane wartości zostały wyeksportowane do programy MS Excel i przedstawione w formie tabelek co ułatwia czytelność uzyskanych wyników.

Tabelki utworze w Excelu eskportujemy z powrotem do Sci Laba w formie macierzy. Przykładowe utworzenie takiej macierzy wygląda następująco:

malejaco =[

0.312002 0.0780005 0.2184014

7.020045 0.2964019 8.0808518

30.654197 0.4836031 53.367942]

Ostatnim krokiem jest wygenerowanie wykresów liniowo-liniowych oraz logarytmiczno-logarytmicznych. Służą do tego polecenia:

plot2d(losowo)

plot2d(losowo, logflag = 'll')

Uzyskane wykresy prezentują się następująco:

Liniowo-linowe dla tabeli wartości rosnących

Logarytmiczno-logarytmiczny dla tabeli wartości rosnących

Liniowo-linowe dla tabeli wartości malejących

Logarytmiczno-logarytmiczny dla tabeli wartości malejących

Liniowo-linowe dla tabeli wartości częściowo uporządkowanych

Logarytmiczno-logarytmicznych dla tabeli wartości częściowo uporządkowanych

Liniowo-linowe dla tabeli wartości losowych

Logarytmiczno-logarytmiczny dla tabeli wartości losowych