====== Sortowanie 1 ======

**Termin zajęć:** 15/16.03.2011

**Do przygotowania:**
  - Teoria:
    - Sortowanie stabilne i niestabilne.
    - Zasada działania algorytmów sortowania:
      - bąbelkowego (BubbleSort),
      - przez wybór (SelectionSort),
      - przez wstawianie (InsertionSort),
      - przez zliczanie (CountingSort).
    - Ograniczenia stosowania w.w. algorytmów.
  - Implementacja funkcji sortujących dla wszystkich w.w. algorytmów:
    - Sortowanie bąbelkowe:<code c>void sortBubble(type* tab, int length)</code>
    - Sortowanie przez wybór:<code c>void sortSelection(type* tab, int length)</code>
    - Sortowanie przez wstawianie:<code c>void sortInsertion(type* tab, int length)</code>
    - Sortowanie przez zliczanie:<code c>void sortCounting(type* tab, int length)</code>
  - W przypadku implementacji algorytmu sortowania przez zliczanie należy wcześniej obliczyć wielkość przedziału wartości w tablicy którą należy posortować. \\ Następnie, na podstawie tego wyniku należy określić wielkość tablicy zliczającej.
  - Proszę przygotować prostą funkcję, która będzie używana do porównywania wartości.<code c>
/*
 * \brief Funkcja porównująca dwie wartości
 * 
 * \param val1 - wartość 1.
 * \param val2 - wartość 2.
 * \return Funkcja zwraca:
 * \li -1 jeżeli val1 > val2
 * \li 0 jeżeli val1 == val2
 * \li 1 jeżeli val1 < val2
*/
int compare(type val1, type val2)
</code>
  - Powyższa funkcja powinna być użyta do **wszystkich** operacji porównywania wartości jaki są wykonywane podczas działania wyżej wymienionych algorytmów.
  - Proszę przygotować prostą funkcję, która będzie używana do wypisywania tablicy:<code c>
/*
 * \brief Funkcja wypisująca wartości tablicy
 * 
 * \param tab - tablica wartosci
 * \param length - wielkość tablicy
*/
void printtab(type* tab, int length)
</code>
  - **type** jest zdefiniowane poprzez **typedef**:<code c>typedef int type;</code>umożliwi nam to szybką zmianę typu na którym będziemy pracowali.
  - Do pomiaru czasu działania algorytmów (na tych oraz późniejszych zajęciach) będziemy używali funkcji **rdtsc**:<code c>
#include <stdint.h>

__inline__ uint64_t rdtsc() 
{
    uint32_t lo, hi;
    __asm__ __volatile__ (
    "xorl %%eax,%%eax \n        cpuid"
    ::: "%rax", "%rbx", "%rcx", "%rdx");
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return (uint64_t)hi << 32 | lo;
}
</code>
  - Funkcja zwraca liczbę cykli procesora od momentu uruchomienia komputera. Do pomiaru czasu działania kodu wykorzystujemy ją następująco:<code c>
uint64_t s,e,d;
...
s = rdtsc();
// kod którego czas wykonania mierzymy
e = rdtsc();
d = e-s;
printf("Czas wykonania kodu d = %lld\n", d);
</code>
  - Bardzo proszę przetestować na swoich systemach operacyjnych czy funkcja **rdtsc** nie jest zablokowana.