[[
✎ pl:dydaktyka:asd:cwiczenia:2012-sort1
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Sortowanie 1 ====== **Termin zajęć:** 20/21.03.2012 **Do przygotowania:** - Teoria: - Sortowanie stabilne i niestabilne. - Zasada działania algorytmów sortowania: - bąbelkowego (BubbleSort), - przez wybór (SelectionSort), - przez wstawianie (InsertionSort), - 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 przez zliczanie:<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.<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 **wszystkich** operacji porównywania wartości jaki są wykonywane podczas działania wyżej wymienionych algorytmów. - 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 **GetTickCount**, **clock** lub **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. 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)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry