\documentclass[10pt,a4paper]{article}

%% Polonizacja
%\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[plmath]{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

%% Listy
\usepackage{enumitem}

%% Programy
\usepackage[!labels]{listings}
\lstloadlanguages{C,C++}
\lstset{
  language=C,
  tabsize=2,
  %% indent=\parindent,   % poprzednia wersja listings
  xleftmargin=\parindent,
  basicstyle=\small,
  commentstyle=\slshape,
  stringstyle=\ttfamily,
  fontadjust=true,
  %% stringspaces=false,  % poprzednia wersja listings
  showstringspaces=false,
  mathescape=true,
  extendedchars=true,
  }

%% Twierdzenia
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{df}{Definicja}[section]

%% Własne polecenia
\DeclareMathOperator{\sign}{sign}
\newcommand*{\abs}[1]{\lvert #1 \rvert}

\begin{document}

\newcounter{seria}
\setcounter{seria}{9}
% 1 - wstęp, dokładność numeryczna
% 2 - wielomiany
% 3 - interpolacja wielomianowa
% 4 - współczynniki wielomianu interpolującego
% 5 - splines
% 6 - kwadratury Gaussa
% 7 - całkowanie: metoda trapezów, Romberga, całkowanie wielowymiarowe
% 8 - rozwiązywanie równań nieliniowych
% 9 - sortowanie (w pamięci)
\newcommand*{\preparedby}{Jakub Narębski}
\input{naglowek.tex}


\section{Sortowanie}
\label{sec:sortowanie}

\emph{Sortowanie} definiuje się następująco: dana jest lista (tablica)
\begin{math}
  q = [a_1, a_2,\dots,a_n]
\end{math}
elementów zbioru liniowo uporządkowanego; trzeba ustawić elementy
w~porządku niemalejącym 
\begin{math}
  a_{i_1} \le a_{i_2} \le \dots \le a_{i_n}
\end{math}.  
Czasami wymaga się dodatkowego warunku \emph{stabilności}: elementy
równe sobie na wyjściu znajdują się w~tej samej kolejności, w~jakiej
znajdowały się na wejściu (np. sortowanie według imienia i~nazwiska).

Często z~sortowanymi elementami związane są dodatkowe dane.  Dla
uproszczenia w~dalszych rozdziałach zakładać będziemy, że sortujemy
liczby całkowite.  Czas działania algorytmu będziemy oceniać na
podstawie liczby \emph{porównań}.


\subsection{Sortowanie przez wstawianie}
\label{sec:insertion-sort}

Sortowanie przez wstawianie, to algorytm stosowany przez większość
graczy do układania kart. Trzymają w~ręku uporządkowane do tej pory
karty i~gdy pojawia się następna, umieszczają ją na właściwym w~danej
chwili miejscu.  Inaczej, dla każdego $i = 2, 3, \dots, n$ trzeba
wstawić $a[i]$ w~już uporządkowaną część tablicy $a[1] \le \dots \le
a[i-1]$.

\begin{lstlisting}{insertionsort}
for (i = 1; i < N; i++) {
  /* a[0] $\le$ a[1] $\le \dots \le$ a[i-1] */ 
  j = i;
  v = a[i];

  /* wstaw a[i] w odpowiednie miejsce w a[0$\ldots$i] */
  while (j > 0 && a[j-1] > v) {
    a[j] = a[j-1]; /* a[j] - wolne miejsce */
    j--;
  }
  a[j] = v;
} 
\end{lstlisting}

Algorytm ten działa w~czasie pesymistycznym $\frac{1}{2} N^2 -
\mathcal{O}(N)$, oczekiwanym $\frac{1}{4} N^2 + \mathcal{O}(N)$.
Ilość wykonanych porównań jest równa liczbie \emph{inwersji}, tzn.
takich par że $a[i] > a[j]$ dla $i < j$, zatem działa bardzo szybko
dla tablic niemal uporządkowanych.  Algorytm ten jest stabilny, prosty
i~łatwo implementowalny.


\subsection{Sortowanie przez selekcję (wybór)}
\label{sec:selection-sort}

Sortowanie przez selekcję polega na układaniu elementów od
najmniejszego w~ciągu.  Dla każdego $i = 1, 2, \dots, n$ trzeba wśród
elementów $a[i], a[i+1], \dots, a[n]$ znaleźć najmniejszy i~wstawić go
w~miejsce elementu $a[i]$, czyli na koniec posortowanego kawałka
tablicy.

\begin{lstlisting}{selectionsort}
for (i = 0; i < N-1; i++) {
  /* a[0] $\le$ a[1] $\le \dots \le$ a[i-1] $\le$ a[i$\ldots$n] */
  imin = i;
  for (j = i+1; j < N; j++) {
    /* znajdź najmniejszy element w a[i$\ldots$n] */
    if (a[j] < a[imin])
      imin = j;
  }
  
  /* zamień miejscami a[imin] i a[i] */
  v = a[imin]; a[imin] = a[i]; a[i] = v;
}
\end{lstlisting}

Algorytm ten działa w~czasie stałym $\frac{1}{2} N^2 -
\mathcal{O}(N)$; zawsze wykonujemy ten sam ciąg porównań.  Algorytm
ten dokonuje tylko $N-1$ przestawień.  Algorytm ten nie jest stabilny.


\subsection{Sortowanie szybkie (quicksort)}
\label{sec:quicksort}

Algorytm ten jest jednym z~najczęściej stosowanych algorytmów
sortowania.  Jest on uważany za najszybszy algorytm sortowania dla
,,losowych'' danych wejściowych, bliski teoretycznej dolnej granicy
szybkości algorytmów sortowania opartych o~porównania elementów.

Jego konstrukcja oparta jest o~zasadę ,,dziel--i--rządź'': aby
posortować tablicę, dzielimy ją na dwie części (tak by wszystkie
elementy lewej części były mniejsze od wszystkich elementów prawej
części) i~sortujemy każdą z~tych części niezależnie.

W~bibliotece standardowej C znajduje się funkcja biblioteczna
\lstinline!qsort! której możemy użyć do sortowania.  Jako jeden
z~argumentów wymaga ona funkcji porównującej elementy.  Funkcja ta
jako argumenty przyjmuje \emph{adresy} obiektów do porównania,
a~zwraca wartość \emph{całkowitą} większą od zera jeśli pierwszy
obiekt jest większy od drugiego, zero jeśli obiekty są równe, mniejszą
od zera jeśli pierwszy obiekt jest mniejszy od drugiego.  $a > b
\implies \text{\lstinline!cmp!}(a, b) > 0$.  Poniżej
znajduje się przykład jej wykorzystania

\begin{lstlisting}{qsort-example}
#include <stdlib.h>
$\ldots$
int compare_double(const void *a, const void *b)
{
  /* rzutujemy na wskaźnik do właściwego typu typ */
  const double *ia = (const double *) a;
  const double *ib = (const double *) b;
  
  /* zwracamy >0 gdy *ia > *ib, 0 gdy *ia == *ib, <0 wpp */
  return (*ia > *ib) - (*ia < *ib);
}
$\ldots$
int a[N];
$\ldots$
qsort(a, N, sizeof(a[0]), compare_double);
\end{lstlisting}

Sortowanie to ma koszt pesymistyczny $\mathcal{O}(N^2)$, oczekiwany
$\mathcal{O}(N \log N)$ (z~małym współczynnikiem proporcjonalności,
rzędu $1.4$), z~silnym skupieniem wokół wartości oczekiwanej.  Można
go ulepszyć by był częściej $\mathcal{O}(N \log N)$ (m. in. dla prawie
posortowanej lu o~większości elementów równych sobie).  Liczba zamian
jest podobna jak liczba porównań.  Algorytm ten zazwyczaj wymaga
dodatkowo $\mathcal{O}(\log N)$ ($\mathcal{O}(N^2)$ w~częsci
implementacji) dodatkowej pamięci, nie jest też stabilny (ale można go
uczynić stabilnym za pomocą porównywania adresów; patrz \texttt{info
  libc}).


\subsection{Sortowanie stogowe (kopcowe)}
\label{sec:heapsort}

Sortowanie stogowe (heapsort) korzysta z~właściwości stogu, struktury
danych która umożliwia dodanie nowego elementu oraz pobranie
i~usunięcie największego elementu w~czasie $\mathcal{O}(\log N)$.
Konstruujemy kopiec z~elementów tablicy, a~następnie \mbox{$N$--krotnie}
pobieramy i~usuwamy największy element ze stogu, uzyskując
uporządkowaną tablicę (podobnie jak w~sortowaniu przez selekcję
(wybieranie)).  Kopiec można umieścić w~sortowanej tablicy, uzyskując
sortowanie za pomocą tylko stałej dodatkowej pamięci.


\subsubsection{Definicja i~właściwości stogu}
\label{sec:wlasc-stogu}

Przez \emph{stóg} (kopiec) rozumiemy drzewo binarne (każdy węzeł ma co
najwyżej dwu potomków) o~dwu własnościach.  Pierwszą z~nich to
\emph{porządek stogowy}: wartość każdego węzła jest nie mniejsza niż
wartości jego potomków.  Drugą własnością stogu jest jego
\emph{kształt}: wszystkie poziomy są wypełnione całkowicie,
z~wyjątkiem co najwyżej ostatniego --- spójnie wypełnionego od strony
lewej.

Dzięki właściwości kształtu można reprezentować kopiec w~tablicy
(kolejnymi poziomami, począwszy od wierzchołka) bez dodatkowych
dowiązań.  W~tej reprezentacji potomkami węzła o~indeksie $k$ są węzły
$2 k$ i~$2 k + 1$, zaś przodkiem węzła $l$ jest węzeł $\lfloor l/2
\rfloor$.  Warunek uporządkowania przyjmuje postać:
\begin{equation*}
  \bigwedge\limits_{2 \le i \le N} a[\lfloor i/2\rfloor] \ge a[i].
\end{equation*}


\subsubsection{Operacje na stogu}
\label{sec:operacje-na-stogu}

Dwie podstawowe operacje na stogu to operacja przywracania
uporządkowania dla stogu do którego wstawiono nowy element do korzenia
(operacja \lstinline!downheap!), oraz stogu do którego wstawiono nowy
element jako jego ostatni element (operacja \lstinline!upheap!).
Poniżej znajdują się implementacje tych dwu procedur ($1 \le k \le N$).  
\begin{lstlisting}{upheap}
void upheap(int heap[], int k)
{
  int v; /* wartość którą wstawiamy */
  int i; /* indeks ojca węzła k */
  
  v = heap[k-1];
  i = k/2;
  while (k > 1 && heap[i-1] < v) {
    heap[k-1] = heap[i-1];
    k = l; i = i/2;
  }
  heap[k-1] = v;
}
\end{lstlisting}
\begin{lstlisting}{downheap}
void downheap(int heap[], int k, int N)
{
  int v; /* wartość którą wstawiamy */
  int j; /* indeks większego z synów węzła k */

  v = heap[k-1];
  while (k <= N/2) {
    j = 2*k;
    if (j < N && heap[j-1] < heap[j+1-1])
      j++;
    if (v >= heap[j-1])
      break;
    heap[k-1] = heap[j-1];
    k = j;
  }
  heap[k-1] = v;
}
\end{lstlisting}
Obydwie procedury wykonują się w~czasie $\mathcal{O}(\log N)$.

Za ich pomocą łatwo jest zaimplementować funkcje \lstinline!insert!
wstawiającą element do kopca w~czasie $\mathcal{O}(\log N)$,
\lstinline!deletemax! usuwająca (i~zwracająca) największy element ze
stogu w~czasie $\mathcal{O}(\log N)$ oraz \lstinline!construct!
budującą stóg z~tablicy w~czasie $\mathcal{O}(N)$.
\begin{lstlisting}{insert}
void insert(int heap[], int *N, int value)
{
  heap[(*N)-1] = value;
  upheap(heap, *N);
  (*N)++;
}
\end{lstlisting}
\begin{lstlisting}{deletemax}
int deletemax(int heap[], int *N)
{
  int max = heap[0];
  
  a[0] = a[(*N)-1];
  (*N)--;
  downheap(heap, 1, *N);
}
\end{lstlisting}
\begin{lstlisting}{construct}
void construct(int heap[], int N)
{
  int i;
  
  for (i = N/2; i >= 1; i--)
    downheap(heap, i, N);
}
\end{lstlisting}


\subsubsection{Implementacja sortowania stogowego (heapsort)}
\label{sec:heapsort-implementacja}

W~sortowaniu stogowym najpierw budujemy stóg z~tablicy, korzystając
\mbox{$N$--krotnie} z~funkcji \lstinline!insert! lub z~funkcji
\lstinline!construct!.  Następnie budujemy uporządkowana tablicę od
końca, zdejmując kolejne największe elementy ze stogu przy pomocy
funkcji \lstinline!deletemax!.

\begin{lstlisting}{heapsort-1}
void heapsort(int a[], int N)
{
  int M;
  
  construct(a, N);
  do {
    M = N;
    a[M] = deletemax(a, &N);
  } while (N > 1);
}   
\end{lstlisting}

Bez utraty prostoty można by napisać sortowanie stogowe używając
wyłącznie funkcji \lstinline!downheap!:
\begin{lstlisting}{heapsort-2}
void heapsort(int a[], int N)
{
  int v;
  int i;
  
  for (i = N/2; i >= 1; i--)
    downheap(a, i, N);
  for (i = N; i >= 2; i--) {
    v = a[i-1]; a[i-1] = a[0]; a[0] = v;
    downheap(a, 1, i-1);
  }
}   
\end{lstlisting}

Sortowanie stogowe ma koszt pesymistyczny $2 N \log N +
\mathcal{O}(N)$.  Wyniki badań pokazują, że oczekiwany współczynnik
przy $N \log N$ jest bliski $2$.  Sortowanie to działa ,,w miejscu'',
t.j. wymaga tylko stałej ilości dodatkowej pamięci (w~przeciwieństwie
do sortowania szybkiego).  Sortowanie stogowe nie jest stabilne.


\subsection{Sortowanie przez scalanie (łączenie)}
\label{sec:mergesort}

Sortowanie przez scalanie to algorytm sortowania używany najczęściej
do sortowania plików.  Algorytm ten działa w~czasie pesymistycznym
$\mathcal{O}(N \log N)$, i~jest on stabilny (w~klasycznej
implementacji).  Algorytm ten wymaga dodatkowej pamięci, tablicy (lub
pliku) pomocniczego, $\mathcal{O}(N)$ --- można tego uniknąć ale
kosztem dużej komplikacji (i~spowolnienia) algorytmu.  Co czyni ten
algorytm szczególnie przydatnym do sortowania plików jest fakt, że
jest on lokalny, i~nie trzeba trzymać w~pamięci całego pliku
(potrzebny jest tylko sekwencyjny dostęp do danych).

\subsubsection{Zapis w postacie rekurencyjnej}
\label{sec:mergesort:rekurencja}

Najprościej zrozumieć sortowanie przez scalanie w~wersji
rekurencyjnej.  Dzielimy tablicę (plik) na połowy,
sortujemy te połówki rekurencyjnie (tablica/plik długości 1 jest już
posortowana), a~następnie łączymy (scalamy) posortowane kawałki ---
stąd nazwa algorytmu.

\begin{lstlisting}[language=C++]{mergesort-1}
template <typename T>
void mergeSort(T a[], int left, int right, T tmp[]) 
{
  if (left >= right) 
    return;

  int middle = (left+right)/2;

  mergeSort(a,     left, middle, tmp);
  mergeSort(a, middle+1,  right, tmp);
  merge(a, left, middle, right, tmp);
}
\end{lstlisting}

Scalanie dwu posortowanych kawałków polega na tym, że do tablicy
(pliku) wynikowego przenosimy zawsze mniejszy z~początkowych elementów
obu części; jeśli jedna z~części zostanie w~całości przeniesiona do
tablicy (pliku) wynikowego to przenosimy tam pozostały kawałek drugiej
części.


\subsubsection{Łączenie proste}
\label{sec:mergesort:proste}

Algorytm sortowania przez scalanie (łączenie) można także zapisać bez
pomocy rekurencji.  Odpowiednikiem wyżej przedstawione wersji
rekurencyjnej jest sortowanie przez tzw. \emph{łączenie proste}:

\hspace{\parsep}
\begin{enumerate}[label=({\alph*}),ref={\alph*},nolistsep]
\item Dzielimy ciąg (tablicę, plik) $a$ na dwie połowy nazwane $b$
  i~$c$.

\item Łączymy ciągi $b$ i~$c$ składając pojedyncze ich elementy w~pary
  uporządkowane. 

\item Nazywamy połącząony ciąg $a$ i~powtarzamy kroki 1 i~2, łącząc
  tym razem pary uporządkowane w~czwórki uporządkowane.

\item Powtarzamy poprzednie kroki łąćząc czwórki w~ósemki itd.,
  podwajając za każdym razem długość łączonych podciągw dopóty, dopóki
  cały ciąg nie zostanie uporządkowany.
\end{enumerate}


\subsubsection{Łączenie naturalne}
\label{sec:mergesort:naturalne}

W~metodzie łączenia prostego nie korzysta się z~ewentualnego,
częsciowego uporządkowania danych źródłowych.  Sortowanie w~którym
zawsze scala się dwa możliwie najdłuższe podciągi nazywamy
\emph{sortowaniem przez łączenie naturalne}.

Metoda ta daje znaczące przyspieszenie dla prawie posortowanych
ciągów, kosztem dodatkowych operacji wymaganych do sprawdzania czy
podciag posortowany już się skończył.  Dodatkowo może obecnie zajść
sytuacja, gdzie dwie części nie będa równej długości, i/lub nie będą
zawierały identycznej ilości podciągów.
\\
%% 
\input{podpis.tex}

\end{document}

