Program "Algorytmy"

Program "Algorytmy" przeznaczony jest do wizualizacji działania podstawowych algorytmów sortowania i wyszukiwania danych. W obecnej wersji są to: sortowanie bąbelkowe, sortowanie przez wybór kolejnych minimów, sortowanie kubełkowe, szybkie sortowanie oraz wyszukiwanie blokowe i wyszukiwanie za pomocą metody bisekcji.

Główne okno programu wygląda następująco:

Prezentację wybranego algorytmu uruchamia się odpowiednim przyciskiem.

Okna prezentacji algorytmów składają się z następujących części:

"tablica z danymi",
"pseudoprogram" (kod IPL - Informal Programming Language),
"wartości używanych zmiennych i statystyka",
"panel kontrolny",
"regulator prędkości",
elementy charakterystyczne dla danego algorytmu.

"Tablica z danymi" w sposób wizualny pokazuje zawartość bloku danych, na którym wykonywane są operacje. Poza tym zaznaczone są tu również, o ile to możliwe, wartości zmiennych indeksujących. Program pokazuje, na który element w danym momencie wskazuje taka zmienna. Oprócz tego w przypadku niektórych algorytmów "tablica z danymi" zawiera jeszcze inne dodatkowe informacje. Do "tablicy z danymi" zalicza się również okienko, za pomocą którego ustala się liczbę danych (5 - 22).

"Pseudoprogram" jest to zapis algorytmu w postaci "pseudokodu". Nie wykorzystuje się tu składni żadnego konkretnego języka programowania, choć w pewnym sensie stosowany tu "pseudokod" przypomina Pascala. W czasie prezentacji algorytmu program Algorytmy symuluje wykonywanie się "pseudoprogramu". Przypomina to opcję śledzenia wykonywania się programów (debugger), dostępną w większości języków programowania.

W części "wartości używanych zmiennych i statystyka", która jest dopełnieniem "pseudoprogramu", pokazywane są aktualne wartości wszystkich używanych w nim zmiennych. Oprócz tego program podaje ilość wykonanych porównań i zamian danych.

"Panel kontrolny"

Poszczególne przyciski panelu, to kolejno od lewej: "nowe losowanie", "stop", "jeden krok", "film", "opis algorytmu", które służą odpowiednio do: wpisania w tablicę nowych losowo wybranych danych, zatrzymania wykonywania algorytmu, wykonania jednego kroku algorytmu, uruchomienia pseudoprogramu (z szybkością ustaloną w "regulatorze prędkości") i wyświetlenia okna pomocy ze skrótową informacją o istocie i właściwościach algorytmu.

"Regulator prędkości" służy do określania szybkości wykonywania się "pseudoprogramu", gdy włączony jest tryb "film" (patrz wyżej).

 

  1. Sortowanie bąbelkowe
  2. W celu zwiększenia czytelności prezentacji zastosowano najprostszą (pozbawioną wszelkich optymalizacji) wersję algorytmu.

    Okno prezentujące ten algorytm wygląda następująco:

    Dodatkową informacją, jaką podaje "tablica z danymi" jest uwaga o wymianie danych. Poza tym element tablicy, który jest najmniejszy z danego przedziału (i; n) drukowany jest pogrubioną czcionką (na rysunku jest to "9") - to on jak bąbelek "wypłynie" na samą górę.

     

  3. Sortowanie przez wybór kolejnych minimów
  4. Okno wizualizujące ten algorytm właściwie nie ma żadnych dodatkowych elementów w porównaniu z poprzednim. Oczywiście odmienna jest treść "pseudoprogramu". Dla tego algorytmu wygląda on następująco:

     

  5. Sortowanie kubełkowe (pozycyjne)
  6. Jak widać, w dolnej części okna znajduje się dodatkowy element - panel z kubełkami, czyli kolejkami, do których wpisywane są dane mające na odpowiedniej pozycji cyfrę równą numerowi kubełka (dokładniejsze informacje można znaleźć w literaturze).

     

  7. Szybkie sortowanie (QuickSort)
  8. Jest to wizualna implementacja algorytmu szybkiego sortowania z wykorzystaniem stosu. Okno prezentujące QuickSort wygląda następująco:

    image18.gif (15110 bytes)

    W "tablicy z danymi" wprowadzono kilka dodatkowych informacji:

    1) Najjaśniejszy kolor mają elementy należące do właśnie przetwarzanego przedziału;

    2) Jasno szary (trochę ciemniejszy od poprzedniego) kolor mają elementy przedziałów czekających na stosie na przetworzenie;

    3) Najciemniejsze kolory mają elementy już przetworzone, tzn. te, które już zostały umieszczone na swoich docelowych miejscach;

    4) W momencie pobierania wartości elementu rozdzielającego x pojawia się okienko o tym informujące:

    image19.gif (6372 bytes)

    5) W momencie zamiany elementów program podświetla elementy, które mają być zamienione:

    image20.gif (4410 bytes)

    6) Dodatkowo wszystkie elementy tablicy równe elementowi rozdzielającemu drukowane są pogrubioną czcionką.

    Obok okienka z "pseudoprogramem" znajduje się okienko reprezentujące stos. Dane przedziałów przeznaczonych do przetworzenia (odłożonych na stosie) zapisane są w następujący sposób:
    i) każda linijka to jeden przedział,
    ii) przedział przedstawiony jest jako (p; k), gdzie p jest indeksem elementu rozpoczynającego przedział, a k indeksem elementu kończącego przedział.

     

  9. Wyszukiwanie metodą bisekcji
  10. Jest to wizualna implementacja znanego algorytmu wyszukiwania za pomocą metody bisekcji, czyli rekurencyjnego dzielenia przedziału na dwa podprzedziały i określania, w którym z nich szukany element może wystąpić. Oczywiście algorytm ten wymaga tablicy z posortowanymi danymi.

    Prezentacja ta wygląda podobnie, jak w przypadku sortowań, za wyjątkiem tego, że na początku "pseudoprogram" pyta o liczbę do znalezienia.

  11. Wyszukiwanie blokowe
  12. W algorytmie tym zastosowano podział posortowanej tablicy danych na bloki w taki sposób, by ich wielkość była zbliżona do pierwiastka z liczby wszystkich elementów. Ten sposób dzielenia tablicy jest najbardziej efektywny. W programie poszczególne bloki w "tablicy z danymi" oddzielone są od siebie poziomymi liniami:



Dla wszystkich algorytmów, oprócz wymienionych powyżej okien, dostępne są również okna z informacjami o każdym z nich, zawierające opisy i skrótowo podane właściwości poszczególnych algorytmów. Dostępne są one po naciśnięciu przycisku "opis algorytmu" na "panelu kontrolnym".

 

Na głównym panelu programu Algorytmy dostępna jest również opcja "Porównanie sortowań". Po jej wybraniu ukazuje się okienko służące do wizualnego porównania szybkości działania uwzględnionych w programie algorytmów sortowania.