Sortowanie 1

Termin zajęć: 20/21.03.2012

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. 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 przez zliczanie:
      void sortCounting(type* tab, int length)
  3. 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.
  4. 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)
  5. 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.
  6. Proszę przygotować prostą funkcję, która będzie używana do wypisywania tablicy:
    /*
     * \brief Funkcja wypisująca wartości tablicy
     * 
     * \param tab - tablica wartosci
     * \param length - wielkość tablicy
    */
    void printtab(type* tab, int length)
  7. type jest zdefiniowane poprzez typedef:
    typedef int type;

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

  8. Do pomiaru czasu działania algorytmów (na tych oraz późniejszych zajęciach) będziemy używali funkcji GetTickCount, clock lub 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;
    }
  9. Funkcja zwraca liczbę cykli procesora od momentu uruchomienia komputera. Do pomiaru czasu działania kodu wykorzystujemy ją następująco:
    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);
  10. Bardzo proszę przetestować na swoich systemach operacyjnych czy funkcja rdtsc nie jest zablokowana. W razie potrzeby proszę poszukać innych funkcji zliczających.
pl/dydaktyka/asd/cwiczenia/2012-sort1.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0