\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{marvosym}
\usepackage{ amssymb }
\usepackage{caption}
\usepackage{indentfirst}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{float}
\addtolength{\textwidth}{3cm}
\addtolength{\hoffset}{-1.5cm}
\addtolength{\textheight}{3cm}
\addtolength{\voffset}{-1.5cm}


\title{Projektowanie Algorytmów i Metody Sztucznej Inteligencji}
\author{Robert Krzyżoś }
\date{March 2019}



\begin{document}

\maketitle

\textbf{ Prowadzący: dr inż. Krzysztof Halawa}
\textbf{ Zajęcia: wtorek 13}

\section{Wstęp}
Celem projektu było samodzielne zaimplementowanie wybranych \mbox{algorytmów} sortujących oraz przeprowadzenie testów ich efektywności. Wybrane algorytmy to sortowanie: szybkie, introspektywne oraz przez scalenie.

Algorytmy sortowania są zazwyczaj klasyfikowane według:
\begin{itemize}
\item złożoności (pesymistyczna, oczekiwana) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru
\item złożoności pamięciowej
\item sposobu działania - tj. sposobu za pomocą którego algorytm uporządkuję naszą strukturę danych
\item stabilności - elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym

\end{itemize}
Wszystkie wybrane algorytmy posiadają logarytmiczną złożoność obliczeniową. Wyjątkiem jest pesymistyczny przypadek quicksorta
\begin{math}
\Omega(n^{2}).
\end{math}
Dwa spośród nich to algorytmy niestabilne tj. quicksort oraz introsort, mergesort należy natomiast do sortowań stabilnych.\\
\indent Testy efektywności polegały na przeprowadzeniu eksperymentów dla 100 tablic o kolejnych rozmiarach: 10000, 50000, 100000, 500000 oraz 1000000 o różnych stopniach uporządkowania: 25\%, 50\%, 75\%, 95\%, 99\%, 99,7\% oraz o wszystkich elementach uporządkowanych, ale w odwrotnej kolejności.

\section{Sortowanie szybkie}
Sortowanie szybkie to jeden z najpopularniejszych algorytmów sortowania, oparty o zasadę dziel i zwyciężaj. Sortowanie to zostało wynalezione w 1962 przez C.A.R. Hoare'a. Jak już wcześniej zostało wspomniane zalicza się on do algorytmów niestabilnych. Średnia żłożoność obliczeniowa wynosi:
\begin{math}
O(nlogn).
\end{math}
Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Sortowania to jest algorytmem rekurencyjnymm. W każdym wywołaniu wybierany jest element rozdzielający tzw. pivot po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, który nie wymaga dalszego sortowania. W przypadku gdy w miejsce pivota za każdym razem wybrany zostaje element największy lub najmniejszy mamy doczynienia z najgorszym przypadkiem algorytmu quicksort. Jego złożoność obliczeniowa wynosi
\begin{math}
O(n^{2})
\end{math}
\newpage
\begin{figure}[th]
    \centering
    \includegraphics[width=0.75\textwidth]{szybkieTabela.png}
    \caption{Tabela z pomiarami czasów sortowań, w zależności od liczby elementów w tablicy oraz stopnia uporządkowania dla sortowania szybkiego.}
    \label{tabSzyb}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.75\textwidth]{SzybkieWykres.png}
    \caption{Wykres przedstawiający graficznie dane z tabeli 1.}
    \label{wykSzyb}
\end{figure}

\newpage
\section{Sortowanie introspektywne}
Sortowanie introspektywne to sortowanie hybrydowe mające na celu wyeliminowanie najgorszego przypadku quicksorta. W algorytmie tym występują sortowania: przez kopcowanie, przez wstawienie oraz sortowanie szybkie. Pomysł sortowania hybrydowego opiera się na spostrzeżeniu, że ogromna liczba rekurencyjnych wywołań algorytmu quicksort jest realizowana dla małych tablic, które są bardzo czasochłonne i zajmują miejsce na stosie. Rozwiązaniem problemu złożoności obliczeniowej
\begin{math}
O(n^{2})
\end{math}
w najgorszym przypadku jest badanie głębokości rekurencji. Maksymalna dopuszczalna głębokość wyznaczona jest na podstawie wzoru:
\begin{math}
M=2*log_{2}n
\end{math}
Jeżeli wartość parametru M wynosi 0, wywołania rekurencyjne są kończone i dla podproblemu, którym obecnie się zajmujemy, wywoływana jest procedura Sortowania Przez Kopcowanie, które jest traktowane jako sortowanie pomocnicze. W celu usprawnienia działania sortowanie szybkiego po zakończeniu rekurencyjnych wywołań procedury quicksort tablica podzielona jest na szereg małych podzbiorów o rozmiarze nie większym niż 9. Nastęnie wywołuje się procedure sortowania przez wstawienie, której zadaniem jest uporządkowanie podtablicy do końca. Sortowanie Przez Wstawianie jest elementarnym algorytmem sortowania, ale posiada liniową złożoność obliczeniową dla uporządkowanych tablic danych.

\begin{figure}[h]
\centering
\includegraphics[width=0.8\textwidth]{introspektywneTabela.png}
 \caption{Tabela z pomiarami czasów sortowań, w zależności od liczby elementów w tablicy oraz stopnia uporządkowania dla sortowania introspektywnego.}
    \label{tabIntro}
\end{figure}
\newpage
\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{sortowanieIntrospektywne.png}
\caption{Wykres przedstawiający graficznie dane z tabeli 2.}
    \label{wykIntro}
\end{figure}

\section{Sortowanie przez scalenie}
Rekurencyjny algorytm sortowania podobnie jak quicksort wykorzystujący metodę dziel i zwyciężaj. Procedura dzieli zestaw danych na dwie części do momentu uzyskania tablic jednoelementowych. Następnie podtablice są porównywane oraz scalane układający elementy w zadanej kolejności. Złożoność obliczeniowa tego algorytmu wynosi:
\begin{math}
O(nlogn),
\end{math}
a w najgorszym przypadku wzrasta jedynie ilość potrzebnych porównań podczas scalania danej tablicy.
\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{scalanieTabela.png}
 \caption{Tabela z pomiarami czasów sortowań, w zależności od liczby elementów w tablicy oraz stopnia uporządkowania dla sortowania przez scalanie.}
    \label{tabScal}
\end{figure}

\newpage
\begin{figure}[th]
\centering
\includegraphics[width=0.8\textwidth]{mergeWykres.png}
\caption{Wykres przedstawiający graficznie dane z tabeli 3.}
    \label{wykScal}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=0.8\textwidth]{porownanie.png}
\caption{Wykres przedstawiający porównanie 3 algorytmów dla losowej tablicy 1000000 elementów}
    \label{por}
\end{figure}

\newpage
\section{Wnioski}


\end{document}