====== 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
   

[[http://www.youtube.com/watch?v=ROalU379l3U|Sortowanie przez wstawianie na folkowo]]\\
[[wp>Insertion_sort|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 : {{zajecia:pp_2013_2:lab_src: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ęć: {{zajecia:pp_2013_2:lab_src: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ę ''[[http://pl.wikibooks.org/wiki/C/clock|clock]]'' z biblioteki ''time.h''. 
Przykład użycia tej funkcji do pomiaru czasu wykonywania  pewnego fragmentu programu:

<code C>
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;
</code>


===== 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