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]

  1. i ← 1
  2. umieść i-ty element A[i] w odpowiednim miejscu ciągu A[0],…,A[i] tak aby ten ciąg pozostał posortowany
  3. i ← i + 1
  4. 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