2011-04-29
Metodyka i Techniki Programowania II
Sortowanie
9
dr inż. Jarosław Bułat
Ćwiczenie 1. Proste sortowanie
Wykorzystując kod z
ródłowy z wykładu nr. 9 (sortowanie - przykład 4.1, lab1.c), posortuj tablicę z
następującymi wartościami:
{ 11, 3, 6, 2, 2, 2, 2, -1, 10, 23, -10 }
Zmodyfikuj program tak aby zamienić funkcję:
int minim( int dane[], int start, int N );
na:
int minim( int dane[], int N );
gdzie: dane to wskaz
nik na początek tablicy a N to długość tej tablicy, zauważ, że wywołując nową
funkcję minim(....) jako pierwszy argument możesz podać dowolny element tablicy np.:
minim( dane+4, N-4 ); albo minim( &dane[4], N-4 );
Ćwiczenie 2. Sortowanie bąbelkowe
Wykorzystując kod z
ródłowy z wykładu nr. 9 (sortowanie - przykład 4.2, lab2.c), posortuj tablicę z
następującymi wartościami:
{ 11, 3, 6, 2, 2, 2, 2, -1, 10, 23, -10 }
1. Oblicz ilość zamian (bąbelków), które muszą być wykonane do posortowania ww. tablicy.
2. Napisz taką 11-sto elementową tablicę, która będzie się sortować najszybciej - podaj ilość
niezbędnych zamian
3. Napisz taką 11-sto elementową tablicę, która będzie się sortować najwolniej - podaj ilość
niezbędnych zamian
Ćwiczenie 3. QuickSort
Wykorzystując kod z
ródłowy z wykładu nr. 9 (sortowanie - przykład 4.3a, lab3.c), posortuj tablicę
z następującymi wartościami:
{ 11, 3, 6, 2, 2, 2, 2, -1, 10, 23, -10 }
1. Zmodyfikuj program tak, aby sortował tablice w porządku malejącym (od największych
liczb do najmniejszych liczb).
2. Oblicz i podaj ilość zamian (przestawień) potrzebnych do posortowania ww. tablicy.
Ćwiczenie 4. qsort(...) - zadania nadobowiązkowe
1. Wykorzystaj funkcję bilbioteczną qsort(...) do posortowania tablicy liczb z ćwiczenia 3 oraz
następującej tablicy stałych znakowych:
{ "xa0", "Aaa","aaa", "111", "aaa", "222", "abc", "abd", "XXX", "1a1",
"ooo" };
2. Zmodyfikuj program z ćwiczenia 3 (QuickSort) tak aby sortował tablicę tekstów z pkt.1.
3. Porównaj szybkość sortowania tablicy liczb z ćwiczenia 1 wszystkimi czterema metodami
(sortowanie proste, bąbelkowe, QuickSort oraz qsort). W celu uzyskania miarodajnych
wyników zmierz czas wykonania wielu (np. 1e6) iteracji każdego z algorytmów.