Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2011-sort1 [2011/03/10 14:22] kkr |
pl:dydaktyka:asd:cwiczenia:2011-sort1 [2011/03/14 11:54] ikaf |
- przez wybór (SelectionSort), | - przez wybór (SelectionSort), |
- przez wstawianie (InsertionSort), | - przez wstawianie (InsertionSort), |
- kubełkowego (BucketSort), | |
- przez zliczanie (CountingSort). | - przez zliczanie (CountingSort). |
- Ograniczenia stosowania w.w. algorytmów. | - Ograniczenia stosowania w.w. algorytmów. |
- Sortowanie przez wybór:<code c>void sortSelection(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 wstawianie:<code c>void sortInsertion(type* tab, int length)</code> |
- Sortowanie kubełkowe:<code c>void sortBucket(type* tab, int length)</code> | - Sortowanie przez zliczanie:<code c>void sortCounting(type* tab, int length)</code> |
- Sortowanie przez zaliczanie:<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. | - Proszę przygotować prostą funkcję, która będzie używana do porównywania wartości.<code c> |
<code c> | |
/* | /* |
* \brief Funkcja porównująca dwie wartości | * \brief Funkcja porównująca dwie wartości |
int compare(type val1, type val2) | int compare(type val1, type val2) |
</code> | </code> |
- Powyższa funkcja powinna być użyta do porównywania wartości podczas działania wyżej wymienionych algorytmów. | - 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. |
- **type** jest zdefiniowane poprzez **typdef**:<code c>typedef int type;</code>umożliwi nam to szybką zmianę typu na którym będziemy pracowali. | - 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. |