To jest stara wersja strony!
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:
void sortBubble(type* tab, int length)
Sortowanie przez wybór:
void sortSelection(type* tab, int length)
Sortowanie przez wstawianie:
void sortInsertion(type* tab, int length)
Sortowanie kubełkowe:
void sortBucket(type* tab, int length)
Sortowanie przez zaliczanie:
void sortCounting(type* tab, int length)
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)
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:
typedef int type;
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:
#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;
}
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);
Bardzo proszę przetestować na swoich systemach operacyjnych czy funkcja rdtsc nie jest zablokowana.