Termin zajęć: 15/16.03.2011

Do przygotowania:

1. Teoria:
   1. Sortowanie stabilne i niestabilne.
   2. Zasada działania algorytmów sortowania:
      1. bąbelkowego (BubbleSort),
      2. przez wybór (SelectionSort),
      3. przez wstawianie (InsertionSort),
      4. kubełkowego (BucketSort),
      5. przez zliczanie (CountingSort).
   3. Ograniczenia stosowania w.w. algorytmów.
2. Implementacja funkcji sortujących dla wszystkich w.w. algorytmów:
   1. Sortowanie bąbelkowe:

      void sortBubble(type* tab, int length)

   2. Sortowanie przez wybór:

      void sortSelection(type* tab, int length)

   3. Sortowanie przez wstawianie:

      void sortInsertion(type* tab, int length)

   4. Sortowanie kubełkowe:

      void sortBucket(type* tab, int length)

   5. Sortowanie przez zaliczanie:

      void sortCounting(type* tab, int length)

3. Proszę przygotować prostą funkcję, która będzie używana do porównywania wartości.

   /*
    * \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)

4. Powyższa funkcja powinna być użyta do porównywania wartości podczas działania wyżej wymienionych algorytmów.
5. type jest zdefiniowane poprzez typdef:

   typedef int type;

   umożliwi nam to szybką zmianę typu na którym będziemy pracowali.

6. Do pomiaru czasu działania algorytmów (na tych oraz późniejszych zajęciach) będziemy używali funkcji rdtsc:

   #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;
   }

7. Funkcja zwraca liczbę cykli procesora od momentu uruchomienia komputera. Do pomiaru czasu działania kodu wykorzystujemy ją następująco:

   unit64_t s,e,d;
   ...
   s = rdtsc();
   // kod którego czas wykonania mierzymy
   e = rdtsc();
   d = e-s;
   printf("d = %lld\n", d);