9

Metodyka i Techniki Programowania II
Sortowanie
dr inż. Jarosław Bułat

2011-04-29

Ćwiczenie 1. Proste sortowanie

Wykorzystując kod ź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 wskaź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 ź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 ź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.