|
|
pl:dydaktyka:asd:cwiczenia:2011-sort1 [2011/03/10 18:48] kkr |
pl:dydaktyka:asd:cwiczenia:2011-sort1 [2019/06/27 15:50] |
====== 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), | |
- kubełkowego (BucketSort), | |
- 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 kubełkowe:<code c>void sortBucket(type* tab, int length)</code> | |
- Sortowanie przez zaliczanie:<code c>void sortCounting(type* tab, int length)</code> | |
- 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 porównywania wartości 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. | |
- 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. | |