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.
0 komentarze