Gotowe instrukcje do pobrania w formie dokumentu do pobrania tutaj:
Instrukcja 1: sortowanie bąbelkowe, sortowanie szybkie
Instrukcja 2: sortowanie przez wybór, sortowanie przez wstawianie
Instrukcja 3: złożoność algorytmów sortujących
W programowaniu istnieje naprawdę bardzo dużo metod sortowania. Zaczynając od najprostszych, kończąc na trudnych i skomplikowanych implementacjach algorytmów. Najważniejszym problemem przy sortowaniu jest to, że każdy algorytm sortujący zajmuje konkretną ilość pamięci obliczeniowej. Tak samo jak każdy program komputerowy, który rozwiązuje problem, posiada zasoby takie jak czas i pamięć i są one wyrażane w czasowej złożoności obliczeniowej. Algorytmy sortujące mają różną czasową złożoność obliczeniową, a przy tym każdy z nich ma różną wydajność. Jeżeli dochodzi do analizy takiego algorytmu przypisywana jest mu klasa złożoności obliczeniowej. Istnieją trzy podstawowe klasy:
- O(1) – klasa, w której algorytm bez względu na to ile danych posiada, wykonuje operacje stale, bez zmian;
- O(n) – klasa, w której algorytm dla każdej danej (n) wykona określoną i stałą liczbę operacji;
- O(n2) – klasa, w której algorytm dla każdej danej (n) wykona operacje proporcjonalnie.
Podstawowe algorytmy sortowania posiadają złożoności czasowe typu O(n2), a dla małych wskaźników n, te czasy sortowania są do przyjęcia. Metody sortowania o takich samych elementach wartości klucza, które mogą zachować początkowy porządek nazywane są algorytmami stabilnymi.
Aby oceniać czasową złożoność obliczeniową należy wziąć pod uwagę porównywanie dwóch danych oraz przestawianie (zamienianie) elementów. Złożoność pamięciowa to będzie ilość potrzebnej pamięci, jaką wykorzysta algorytm sortujący w celu uporządkowania danych, bez pamięci na przechowanie zawartych danych. Algorytmy, które posiadają klasę O(1) stałą są zaliczane do algorytmów sortujących w miejscu. Są to takie implementacje, które oprócz pamięci na informacje potrzebuje stałą ilość pamięci na uporządkowanie ich.
W celu wykonania eksperymentu, w jakim czasie sortują podane wyżej algorytmy sortowania, stworzymy program. Aplikacja będzie wypełniać tablicę losowymi liczbami, ilość liczb podawana będzie przez użytkownika, następnie algorytmy sortujące uporządkują dane od najmniejszego do największego. Nasza aplikacja zmierzy czasy sortowań i wypisze je na ekran.
Standardowo zaczynamy od dodania bibliotek do naszego programu, a będzie to „iostream”, „time.h”, oraz „windows.h”. Dodatkowo umieszczamy linijkę z „using namespace std”, która poinformuje kompilator o tym by wszystkie funkcje, nie wymagały użycia przedrostka „std”.
Dodawanie bibliotek.
Następnie definiujemy zmienne ile, zegar oraz czas. Należy to zrobić by kompilator wiedział, jakiego typu są to dane. Dalej dodajemy do programu nasze funkcje z algorytmami sortowania.
Kod przedstawiający implementację zegara oraz funkcji z algorytmami sortującymi.
Kolejnym krokiem jest umieszczenie głównej funkcji „main”, dodanie napisów na ekran, oraz wczytanie do programu ile losowych liczb ma zawierać dynamiczna tablica.
Wypisanie tekstów na ekran.
Następnie przypisujemy dynamiczną alokację tablicy. Robimy to po to, ponieważ z założenia nie wiemy ile wartości znajdzie się w tablicy. Nie musimy określać górnej granicy gdyż tablica będzie rozszerzać się o pola dynamicznie. Do zrobienia tego używa się wskaźników.
Przypisanie dynamicznej alokacji tablicy.
Kolejnym krokiem jest zainicjowanie generatora liczb losowych oraz wypełnienie nimi tablicy. Do generacji używamy komendy srand(). Następnie musimy przepisać wartości z pierwszej tablicy do dwóch pozostałych, tak żeby dane wszędzie były jednakowe.
Zainicjowanie generatora liczb losowych.
Kolejnym etapem jest wywołanie napisów na ekran, rozpoczęcie odliczania zegara, wywołanie funkcji sortowania, zatrzymanie czasu zegara, obliczenie wartości czasu sortowania i wypisania go na ekran. Należy powtórzyć te czynności przy każdym sortowaniu.
Na koniec należy zwolnić pamięć, którą przydzieliliśmy dynamicznie. Wykorzystuje się do tego operatora „delete”. Musimy pamiętać także o nawiasie kwadratowym, ponieważ nasz wskaźnik był tablicą rekordów. Po tej operacji kończymy program operatorem „return 0”, oraz zamykając nawias funkcji głównej.
Sortowanie przez wstawianie należy również do prostych, tak samo jak sortowanie przez wybór. Różni się jedynie metodą wykonania, a mianowicie następne elementy z uporządkowanej tablicy są wycinane i wstawiane we właściwe miejsce dodatkowej posortowanej już listy.
Metoda polega na sprawdzaniu sąsiadujących obok siebie cyfr. Pierwszy element porównywany jest z drugim, jeżeli liczba jest większa, wstawiana jest na początek. Następnie sprawdzany jest element trzeci, który porównywany jest z dwoma poprzednimi, dalej czwarty, zestawiany z trzema początkowymi, itd.
Specyfikacja problemu sortowania przez wstawianie.
Lista kroków przedstawiająca rozwiązanie algorytmu sortowania przez wybór.
Schemat blokowy zawierający algorytm sortowania przez wstawianie.
W podanym przypadku sortowanie rozpoczynamy od końca listy, dlatego zmienną j będziemy zmniejszać. Ze wszystkich elementów zostaje wybierany jeden, następnie umieszczamy go w naszej zmiennej pomocniczej a. Pętla zewnętrzna zajmuje się ustawianiem miejsc od ostatniego do pierwszego, natomiast pętla wewnętrzna szuka uporządkowania dla podanych wartości w tablicy oraz ustawia je w tej tablicy tak, by wartości były posortowane. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od ostatniego do pierwszego, tablica będzie posortowana.
Program sortujący dane metodą sortowania przez wstawianie.
Sortowanie przez wybór jest metodą najprostszą z sortowania. W tablicy należy znaleźć najmniejszy element i zamienić go miejscem z pierwszym elementem tablicy. Jeżeli najmniejszy element występuje wielokrotnie to trzeba wziąć pod uwagę ten, który znajduje się najbliżej początku tablicy.
Następnie we fragmencie tablicy, który obejmuje elementy od drugiego do ostatniego poszukiwane jest minimum i należy zamienić je miejscem z drugim elementem tablicy. Należy tak postępować dodając za każdym razem element do posortowanej części aż nastąpi ostatni element tablicy.
Podany problem sortowania przez wybór można przedstawić w kilku rozwiązaniach. Zaczynamy od specyfikacji problemu, która wyjaśni, jakie dane mamy, jakich potrzebujemy oraz jakich pomocniczych zmiennych będziemy używać.
Specyfikacja problemu sortowania przez wybór.
Lista kroków przedstawiająca rozwiązanie algorytmu sortowania przez wybór.
Schemat blokowy zawierający algorytm sortowania przez wybór.
Schemat blokowy zawiera dwie pętle sterujące wartościami i oraz j. Zewnętrzna steruje wartością zmiennej j, która wyznacza elementy zbioru od 1 do k-1. Algorytm ustawia element najmniejszy jako pierwszy element zbioru. Druga pętla (wewnętrzna) steruje zmienną i oraz porównuje resztę elementów z wartością minimalną. Pętla będzie sprawdzać czy element zbioru t[i] jest mniejszy od elementu t[pmin]. Jeżeli tak to znaleziony został nowy element minimalny. Kiedy pętla wewnętrzna zakończy swoje działanie wartość pmin będzie zawierać indeks elementu minimalnego. Następnie algorytm zamieni miejscami element t[j] z t[pmin], dzięki temu element minimalny znajdzie się w tej pozycji, której powinien. Zwiększając wartość j algorytm przechodzi do następnego elementu zbioru, wykonuje pętlę zewnętrzną.
Program sortujący dane zawarte w tablicy 10-cio elementowej metodą przez wybór.
Algorytm szybkiego sortowania stosuje się najczęściej w programach i jest on najważniejszym sposobem sortowania. Jest również trudniejszy i wykorzystywany w większych bazach danych. Cechuje się niezmierną szybkością wykonania, dzieleniem danego problemu na mniejsze i rozwiązywanie ich następuje rekurencyjnie, wszystkie rozwiązane podproblemy łączą się ze sobą tworząc pełne rozwiązanie. Rekurencja, inaczej rekursja to sytuacja, kiedy funkcja odwołuje się do samej siebie. Tworzy ona swoje kopie aż do napotkania momentu,
w którym funkcja może już wyznaczyć wynik.
Mottem szybkiego sortowania jest dziel i zwyciężaj, które jest jednoznaczne do tego by ułatwić programowanie szybszym i sprytniejszym sposobem. Jeżeli trudno jest posortować dużą tablicę, dzielona jest ona na mniejsze, takie, które jest szybko uporządkować, do momentu aż nie zostanie już nic do sortowania.
Przy tym typie sortowania, na początek wybierana jest oś, czyli losowa liczba z tablicy, która jest linią podziału listy na dwie mniejsze. Liczby mniejsze od osi ustawiane są na lewo tablicy, natomiast większe na prawo. Zostają stworzone dwie tablice do posortowania. Kolejnym krokiem jest wyznaczenie następnych osi tych dwóch list oraz ustawienie liczb według podanego wcześniej schematu. Pojawiają się tym sposobem coraz mniejsze tablice, a także liczby w kolejności uporządkowanej.
Do oddzielenia liczb mniejszych na lewo, większych na prawo komputer posłuży się algorytmem partycjonującym, czyli takim, który podzieli dany zbiór na podzbiory według jakiegoś kryterium.
Specyfikacja problemu szybkiego sortowania.
Lista kroków sortowania szybkiego.
Sortowanie bąbelkowe należy do metod dość instynktownych
jednak jest to metoda bardzo wolna.
Polega ona na porównywaniu dwóch następnych elementów w tablicy i zamianie ich zgodnie z zasadą taką, że jeżeli wykonujemy sortowanie rosnące, to liczba mniejsza zostaje zamieniona na początek, a jeśli jest to sortowanie malejące, to liczba większa zapisana jest na przodzie. Porównywanie elementów rozpoczynane jest od tyłu tablicy. Po jednym przejściu listy należy powtórzyć czynność tyle razy ile liczb w tablicy.
Polega ona na porównywaniu dwóch następnych elementów w tablicy i zamianie ich zgodnie z zasadą taką, że jeżeli wykonujemy sortowanie rosnące, to liczba mniejsza zostaje zamieniona na początek, a jeśli jest to sortowanie malejące, to liczba większa zapisana jest na przodzie. Porównywanie elementów rozpoczynane jest od tyłu tablicy. Po jednym przejściu listy należy powtórzyć czynność tyle razy ile liczb w tablicy.
Lista kroków przedstawiająca rozwiązanie algorytmu sortowania bąbelkowego.
K01: Dla j = 1,2,...,k - 1: wykonuj K02
K02: Dla i = 1,2,...,k - 1: jeśli t[i] > t[i + 1], to t[i] ↔ t[i + 1]
K03: Zakończ
Schemat blokowy sortowania bąbelkowego
Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienną j. Wykonuje się ona k - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również k - 1 razy. Sortowanie odbywa się wewnątrz pętli nr 2. Kolejno porównywany jest i-ty element z elementem następnym. Jeśli elementy te są w złej kolejności, to zostają zamienione miejscami.
Implementacja kodu źródłowego programu sortującego dane metodą sortowania bąbelkowego.
Każdy człowiek, jeden świadomie inny
niekoniecznie, rozwiązując problem tworzy pewne algorytmy. Algorytm jest to
lista kroków lub schemat pokazujący rozpisane czynności dążące do wykonania założonego
celu. Spotykamy się z nimi niemal na każdym kroku, nawet wtedy, kiedy musimy
ugotować obiad czy wyprasować ubranie. Nie każdy zastanawia się nad tym,
ponieważ są to czynności, które wykonujemy codziennie lub bardzo często. Jednak,
gdy przyjrzymy się temu bardziej, zauważymy, że w wielu sytuacjach kolejność
działań powinna zostać zachowana oraz to, że każda czynność ma swój powtarzalny
algorytm. Tworzenie algorytmu przez człowieka zaczyna się tam gdzie pojawia się
problem do rozwiązania. Na wstępie rozważane zostają sposoby na poradzenie
sobie z tym problemem, a wreszcie tworzona jest lista kroków, dokładna i
szczegółowa, dzięki której człowiek wie, co i jak ma robić by osiągnąć cel. Programowanie
wykorzystywane jest w wielu dziedzinach naszego życia. Jak można się domyślić
bez algorytmu nie ma programowania, gdyż to one sprawiają, że nasz program
będzie robił to, co założyliśmy na początku. Programowanie występuje wszędzie,
w naszych nowoczesnych pralkach i lodówkach, telefonach, telewizorach i
tabletach, na naszym koncie w banku. Jest metodą na zarabianie pieniędzy, a także
sposobem na rozwijanie pasji i kreatywności oraz sprawia, że nasze życie staje
się łatwiejsze.
Trochę historii...
Pierwsza wersja języka C++ pojawiła się w
roku 1979. Została opracowana przez duńskiego informatyka, profesora Texas
A&M University w Stanach
Zjednoczonych, Bjarne Stroustrup’a , który został uznany za jednego z
najlepszych naukowców w USA. Stroustrup
rozszerzył język C, dodał obiekty, a także inne elementy z już znanych mu
języków programowania. W latach kolejnych sposób programowania ciągle ulegał
zmianie. Dodawane były różne wersje języka C++, ukazywały się kompilatory,
powołany został zespół do spraw normalizacji, tak by funkcje i schemat języka
pozostał taki sam. Znane firmy komputerowe przedstawiały pierwsze
implementacje.
Wreszcie w 1994r. ANSI (ang. American
National Standards Institute) przyjął oficjalnie standard języka C++ i jest on
wykorzystywany do dziś, wszędzie tam gdzie nie można zastosować niezwykle
popularnego i wszechobecnego języka Java. Znacznie lepiej stosować język C++
przy sortowaniu bardzo dużej ilości danych w bazie, jest bardziej wydajny i ma
ogromne zasoby. Wykorzystywany jest np. w znacznej części gier komputerowych,
programów, telekomunikacji, a także robotyce.
Według jednego z rankingów holenderskiej
firmy TIOBE zajmującej się statystykami dotyczącymi języków programowania,
język C++ znajduje się na 3 miejscu (rys. 1) . Ranking ten dotyczył rocznego
bilansu popularności znanych języków programowania, które wyszukiwane były za
pomocą przeglądarek internetowych. Z dostępnych rankingów w Internecie udało
się znaleźć także spis najlepszych języków programowania wybranych przez
użytkowników serwisu HackerEarth. Na rys. 2 przedstawiony jest wykres kołowy
zawierający preferencje użytkowników, jeśli chodzi o języki programowania.
Język C++/ C wybierany jest chętniej ze względu na to, iż jest prosty w nauce,
możemy tworzyć w nim aplikacje przenośne, dlatego jest ciągle wysoko w
rankingach dotyczących zagadnienia języków programowania.
Podstawowe składniki programowania obiektowego:
- klasa – podstawowy element programu, który w swojej budowie zawiera cechy obiektu, które są dla nich takie same. Klasa jest definicją typu danych.
Podstawowe mechanizmy programowania
obiektowego:
- abstrakcja – proces polegający na uproszczeniu, odrzuceniu cech nieistotnych, natomiast zajęcie się cechami bazowymi, tworzy pojęcie ogólne;
- enkapsulacja – ukrywanie zbioru danych oznaczających stany, w których znajduje się obiekt (pól), oraz zbiorów operacji pozwalających na zmianę aktualnego stanu (metod) dla klas zewnętrznych;
- dziedziczenie – współdzielenie funkcji pomiędzy klasami w programie komputerowym. Klasa może dziedziczyć po innej klasie pola i metody oprócz tego ma swoje;
- polimorfizm – wielopostaciowość w wartościach, zmiennych i podprogramach, „(…) mechanizm pozwalający na wywołanie różnych wersji implementacji metod obiektu w zależności od aktualnego typu obiektu.”
Programowanie strukturalne polega na uporządkowaniu kodu,
w którym zawiera się użycie pętli, instrukcji warunkowych, instrukcji
iteracyjnych, wyrażenia wykonywane są w wyznaczonej kolejności. Struktury
tworzą nadprogramy, które są ułożone w pewnej kolejności, oddziałują między
sobą poprzez interfejsy, są wykonywane jeden po drugim, a w całości tworzą daną
aplikację. Rys.
Struktury algorytmiczne
wykorzystywane w programowaniu strukturalnym to:
- selekcja
- sekwencja
- iteracja
- rekursja
Nie używa się natomiast instrukcji skoku (goto), która
przekazuje sterowanie w zadane programowi miejsce. Istnieje rozdzielenie
pomiędzy definiowaniem danych oraz implementacją funkcji.Selekcja w programowaniu to powiązanie ze składową
strukturą danych. Odwołanie to umożliwia programiście przypisać określoną
wartość np. do pól oraz metod, pobierać wartości, a także wywoływać
podprogramy.
Sekwencja charakteryzuje się pewnym uporządkowaniem
znaków, nazw, symboli. Podprogramy ułożone są w określonej formule przez
programistę, wykonują się one jeden po drugim.
Iteracja inaczej powtarzanie jest czynnością ponawiania po
wielokroć tej samej instrukcji w pętli. Iteracją może być ciągłe zwiększanie
liczby o jeden i jest to tak zwana inkrementacja, lub zmniejszanie jej, czyli
dekrementacja.