Zajęcia 7 (07/01/2014)

Sortowanie przez wstawianie

Zaimplementuj funkcję realizującą sortowanie za pomocą algorytmu przez wstawianie (insert sort) ciągu n liczb rzeczywistych.

Dane: tablica zawierająca ciąg liczb rzeczywistych oraz liczba całkowita n
Wynik: funkcja nie zwraca wartości. W wyniku jej działania otrzymujemy uporządkowany rosnąco ciąg n liczb w tablicy

Algorytm: sortowanie przez wstawianie ciągu A[0], A[1], ... , A[n-1]

i ← 1

umieść i-ty element A[i] w odpowiednim miejscu ciągu A[0],...,A[i] tak aby ten ciąg pozostał posortowany

i ← i + 1

jeżeli i < n wróć do punktu 2

Sortowanie przez wstawianie na folkowo
Insertion sort

Napisz program, który wygeneruje ciąg n losowych wartości rzeczywistych (wykorzystaj w tym celu funkcję do losowania z poprzednich zajęć) a następnie posortuje te liczby za pomocą algorytmu sortowanie przez wstawianie. Ostatecznie program wyświetli posortowany ciąg liczb. Zakładamy, że n<1000.

Program realizujący generowanie ciągu liczb losowych : losowanie.c

Przykład:

n=5
3.53674
65.0011
501.54000
666.5555
991.0000

Sortowanie przez wstawianie - rozszerzenie

Spróbuj zadeklarować jak największą tablicę liczb zmiennopozycyjnych

Wypełnij ją losowymi wartościami

Zmierz i wyświetl czas (w sekundach) potrzebny do posortowania wszystkich elementów tak dużej tablicy za pomocą algorytmu sortowania przez wstawianie

Wykonaj to samo dla algorytmu sortowania przez wybieranie
Program implementujący alg. sortowania przez wybieranie z poprzednich zajęć: sort_select.c. Zdabaj o to aby porównanie czasu wykonania obu algorytmów było wykoanane dla takich samych danych wejścioweych (dla takiego camego ciągu losowych wartości).

Ile sekund potrzebują oba te algorytmy aby posortować 10000, 20000, 30000, 40000 ? Jak zmienia się czas wykonania w zależności od ilości elementów?

Do pomiaru czasu wykonywania poszczególnych procedur wykorzystaj funkcję clock z biblioteki time.h. Przykład użycia tej funkcji do pomiaru czasu wykonywania pewnego fragmentu programu:

float seconds; clock_t tik, tak; tik = clock(); /*Tutaj umiesc fragment kodu do zmierzenia czasu */ tak = clock(); seconds = 1.0*(tak - tik) / CLOCKS_PER_SEC;

Sortowanie przez wstawianie - dalsze rozszerzenie

Rozszerz program w ten sposób aby oprócz porównania czasu wykonania sortowania losowych wartości wyświetlany był również czasu sortowania dla następujących przypadków:

tablica pierwotnie zawiera elementy w rosnącej kolejności

tablica zawiera pierwotnie elementy w malejącej kolejności