Programowanie C++

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.

Programowanie w życiu codziennym.

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.

Archiwum

Lista polecanych artykułów