Algorytmy - przydatne na klasówce

KLASÓWKA Z INFY:
1. Narysuj i opisz przeznaczenie skrzynki (wprowadzenie/wyprowadzenie danych)
2. Wykonaj schemat dla problemu: Obliczanie objętości kuli
3. Wykonaj schemat blokowy dla problemu: Adam odwiedzi w piątek babcię. W sobotę przed południem, jeżeli nie będzie padało Adam wybierze się do ogrodu botanicznego, a wieczorem zaprosi Anię do kina, jeżeli tylko wróci ona z Krakowa. W przeciwnym przypadku obejrzy z Olkiem mecz w telewizji.
4. Opisz mechanizm i cechy sortowania bąbelkowego
5. Wykonaj sortowanie bąbelkowe , tak aby uzyskać ciag roznący, dla ciągu: 55, 9, 44, 6, 33, 10
6. Ile obrotów pętli (dużych kroków) wykona się przy sortowaniu przez proste wybieranie dla ciągu: 60, 11, 20, 13, 25, 26, 30, 44, 49. Jaka będzie złożoność obliczeniowa dla tego ciągu. Uzasadnij odpowiedź.

LISTA KROKÓW ALGORYTMU SORTUJĄCEGO PRZEZ PROSTE WYBIERANIE
1. Zmiennej pomocniczej i przypisz wartość 0.
2. Znajdź minimum we fragmencie tablicy.
3. Zmień miejscami z minimum położonym najbliżej początku tablicy.
4. Wartość zmiennej i zwiększ o 1.
5. Jeśli i
6. Zakończ

CECHY SORTOWANIA PRZEZ PROSTE WYBIERANIE:
-wyszukiwanie elementu mającego się znaleźć na danej pozycji
-zamiana miejscami z tym elementem, który tam jest obecnie
-operacja wykonywana dla wszystkich indeksów sortowanej tablicy
-dla takich samych wielkościowo tablic, można uzyskać różne czasy sortowania
-rozważa się wszystkie elementy tablicy źródłowej, wybiera ten z najmniejszym kluczem by wstawić go w określone miejsce ciągu wynikowego

CECHY SORTOWANIA BĄBELKOWEGO:
-sortowanie o złożoności czasowej i pamięciowej
-porównywanie dwóch kolejnych elementów
-zmienia ich kolejności (jeżeli zaburza ona porządek w jakim sortuje się tablice)
-sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmieny
-w jego działaniu występuje sekwencja operacji zamiany dwóch sąsiadujących elementów (operacja porównaj-zmień)
-elementy "lżejsze/mniejsze przesuwają się na początek ciągu
-rozpoczynamy od pierwszego elementu tablicy

MECHANIZMY SORTOWANIA BĄBELKOWEGO:
Idea sortowania bąbelkowego polega na porównywaniu ze sobą dwóch sąsiednich elementów. Jeżeli element na dalszej pozycji ma wartość mniejszą od elementu go poprzedzającego, oznacza to, że są one w złej kolejności i należy je między sobą wymienić.
W jednym kroku algorytm przechodzi przez cały ciąg i porównuje ze sobą kolejne pary, zamieniając elementy kiedy zajdzie potrzeba. W ten sposób element największy "wypłynie" na ostatnią pozycję niczym bąbelek powietrza na powierzchnię wody (stąd nazwa algorytmu). W kolejnym kroku wystarczy więc zająć się ciągiem o jeden element krótszym (największy jest już na właściwej pozycji). Warto zauważyć, że do posortowania n-elementowej tablicy wystarczy n-1 kroków, gdyż inaczej w ostatnim kroku sortowana byłaby tablica jednoelementowa.

STRZAŁKI ŁĄCZĄCE-Poszczególne elementy schematu łączy się za pomocą strzałek. W większości przypadków blok ma jedną strzałkę wchodzącą i jedną wychodzącą, lecz są także wyjątki (omówię je poniżej).
BLOK STARTOWY/KOŃCOWY: Ta figura oznacza początek lub koniec algorytmu. W każdym algorytmie musi się znaleźć dokładnie jedna taka figura z napisem "Start" oznaczająca początek algorytmu oraz dokładnie jedna figura z napisem "Stop" oznaczająca koniec algorytmu. Najczęściej popełnianym błędem w schematach blokowych jest umieszczanie kilku stanów końcowych, zależnych od sposobu zakończenia programu. Jest to niedopuszczalne, w programie mamy przecież dokładnie jedną instrukcję "end." Blok symbolizujący początek algorytmu ma dokładnie jedną strzałkę wychodzącą a blok symbolizujący koniec ma co najmniej jedną strzałkę wchodzącą.
BLOK WYKONAWCZY: Jest to figura oznaczająca proces. W jej obrębie umieszczamy wszelkie obliczenia lub podstawienia. Proces ma dokładnie jedną strzałkę wchodzącą i dokładnie jedną strzałkę wychodzącą.
BLOK WARUNKOWY-Romb symbolizuje blok decyzyjny. Umieszcza się w nim jakiś warunek (np. "x>2"). Z dwóch wybranych wierzchołków rombu wyprowadzamy dwie możliwe drogi: gdy warunek jest spełniony (strzałkę wychodzącą z tego wierzchołka należy opatrzyć etykietą "Tak") oraz gdy warunek nie jest spełniony. Każdy romb ma dokładnie jedną strzałkę wchodzącą oraz dokładnie dwie strzałki wychodzące.
WPROWADZENIE/WYPROWADZENIE DANYCH: Równoległobok jest stosowany do odczytu lub zapisu danych. W jego obrębie należy umieścić stosowną instrukcję np. Read(x) lub Write(x) (można też stosować opis słowny np. "Drukuj x na ekran"). Figura ta ma dokładnie jedną strzałkę wchodzącą i jedną wychodzącą.
PROCES UPRZEDNIO ZDEFINIOWANY: Ta figura symbolizuje proces, który został już kiedyś zdefiniowany. Można ją porównać do procedury, którą definiuje się raz w programie, by następnie móc ją wielokrotnie wywoływać. Warunkiem użycia jest więc wcześniejsze zdefiniowanie procesu. Podobnie jak w przypadku zwykłego procesu i tu mamy jedno wejście i jedno wyjście.
ŁĄCZNIK STRONNICOWY:Koło symbolizuje tzw. łącznik stronicowy. Może się zdarzyć, że chcemy "przeskoczyć" z jednego miejsca na kartce na inne (np. by nie krzyżować strzałek). Możemy w takim wypadku posłużyć się łącznikiem. Umieszczamy w jednym miejscu łącznik z określonym symbolem w środku (np. cyfrą, literą) i doprowadzamy do nie go strzałkę. Następnie w innym miejscu kartki umieszczamy drugi łącznik z takim samym symbolem w środku i wyprowadzamy z niego strzałkę. Łącznik jest często porównywany do teleportacji (z jednego miejsca na kartce do drugiego). Łączniki występują więc w parach, jeden ma tylko wejście a drugi wyjście.
ŁĄCZNIK MIĘDZYSTRONNICOWY: Ten symbol to łącznik międzystronicowy. Działa analogicznie jak pierwszy, lecz nie w obrębie strony. Przydatne w złożonych algorytmach, które nie mieszczą się na jednej kartce. Uwaga: jeśli stosujemy oba typy łączników w schemacie, to najlepiej jest stosować liczby do identyfikowania jednych i litery do drugich. Dzięki temu nie dojdzie do pomyłki.

ZŁOŻONOŚCI OBLICZENIOWEJ ALGORYTMU: wykonuje mniejszą liczbę operacji w celu uzyskania wyniku. Na złożoność obliczeniową składa się złożoność czasowa i pamięciowa.
ZŁOŻONOŚĆ PAMIĘCIOWA: cecha algorytmu, wynika z liczby i rozmiaru danych wykorzystywanych w algorytmie. Wyznacza zależność rozmiaru pamięci potrzebnej do realizacji algorytmu od wielkości danych wejściowych, może wymagać różnej wielkości pamięci, jest najczęściej proporcjonalna do liczby zmiennych użytych w algorytmie.
ZŁOŻONOŚĆ CZASOWA: pozwala oszacować czas potrzebny do wykonania algorytmu. Wyznacza zależność czasu potrzebnego do wykonania algorytmu od rozmiaru danych wejściowych.

PORÓWNANIE SORTOWANIA BĄBELKOWEGO ZE SORTOWANIEM PRZEZ PROSTE WYBIERANIE:
Wydajniejszym sortowaniem jest przez proste wybieranie, ponieważ liczba przesunięć była mniejsza oraz czas wykonywania operacji sortowania.

:= instrukcja przypisana

* operacja mnożenia

/ operacja dzielenia

div operacja dzielenia całkowitego

mod reszta z dzielenia całkowitego