Uwagi ogólne.

Sprawozdanie z wykonania poniższych zadań (przesłane email-em pod koniec zajęć) powinno zawierać:  

Każda implementacja algorytmu musi zliczać tzw operacje dominujące. W przypadku sortowania i wyszukiwania mogą to być operacje porównywania elementów ciągu.

Programy należy pisać w języku C lub w Pascal-u. W poniższych zadaniach powinno się używać następujących "prototypów" i zmiennych: 

    /*
        język C 
    */

    long int Czas; 
      // zmienna globalna do zliczania operacji dominujących

    void SortPrzezWstawianie(int *tab, int i1, int i2)
    {
      // "i1" i "i2" to zakres elementów tablicy "tab"
      // który zamierzamy posortowac, tj sortujemy elementy
      // tab[i1], tab[i1+1], ..., tab[i2-1], tab[i2]
    }

    void SortPrzezSelekcje(int *tab, int i1, int i2)
    {}

    int CzyJestElementWyszProste(int *tab, int *poz, int elem, int i1, int i2)
    {}
    int CzyJestElementWyszBinarne(int *tab, int *poz, int elem, int i1, int i2)
    {}

    void KopiujTablice(int *tab_zrodlo, int *tab_cel, int i1, int i2);
    {
      // kopiuje tab_zrodlo do tab_cel 
      // (tylko elementy z zakresu i1,i2)
    }

    void LosoweGenerowanieCiaguLiczb(int *tab, int i1, int i2)
    {
      // generuje losowo liczby i umieszcza je w tablicy "tab"
      // (tylko w zakresie i1,i2)
    }

    void PokazTablice(int *tab, int i1, int i2)
    {}

    int tablica[1000], tablica2[1000];
      // te tablice zawierają ciąg liczb;
      // są potrzebne dwie tablice aby można było 
      // porównać działanie dwóch procedur sortujących
      // na tych samych danych !

    main()
    {
        LosoweGenerowanieCiaguLiczb(tablica2,0,19);
        PokazTablice(tablica2);
        
        KopiujTablice(tablica2,tablica,0,19);
        Czas=0;
        SortPrzezWstawianie(tablica,0,19);
        printf("czas działania SortPrzezWstawianie = %li\n", Czas);
        PokazTablice(tablica);

        KopiujTablice(tablica2,tablica,0,19);
        Czas=0;
        SortPrzezSelekcje(tablica,0,19);
        printf("czas działania SortPrzezSelekcje = %li\n", Czas);
        PokazTablice(tablica);

    }
 

"Naiwne" sortowanie.

Problem sortowania:
Dany jest ciąg liczb. Należy zmienić kolejność liczb tak aby otrzymać ciąg niemalejący.
 
UWAGA:
Wszystkie procedury sortowania mają dokonywać tzw sortowania w miejscu tj wszystkie operacje muszą być wykonywane na pojedyńczej tablicy (tej w której znajduje się wejściowy ciąg liczb).
 
Zadanie 1
(sortowanie przez wstawianie)
Zaimplementuj procedurę sortowania przez wstawianie: 
    void SortPrzezWstawianie(int *tab, int i1, int i2)
    {
      // sortuje elementy tablicy tab (tylko z zakresu i1,i2)
    }
Ciąg liczb dzielimy na dwie części: posortowaną "S" i nieposortowaną "NS".  Bierzemy pierwszy z brzegu element części "NS" i sprawdzamy w które miejsce części "S" powinien być wstawiony.  Oczywiście wymaga to przesunięcia elementów "S". Część "S" wydłuża się o jeden element, część "NS" traci jeden elemetnt.  Z pewnych względów warto przeszukiwanie części "S" zaczynać od tyłu (dlaczego ?). 
               "S"        ||             "NS"
    1    5    15    95    ||   7    3    84    85    86
            ^                  |
            |                  |
            --------------------

               "S"             ||        "NS"
    1    5    7     15    95   ||   3    84    85    86
       ^                            |
       |                            |
       ------------------------------

    (i tak dalej ...)
Zbadaj czas działania (czyli ilość operacji dominujących) dla:
  1. losowego ciągu liczb
  2. posortowanego rosnąco ciągu różnych liczb
  3. posortowanego malejąco ciągu różnych liczb
  4. ciągu liczb składającego się z jednej i tej samej liczby
Zadanie 2
(sortowanie przez selekcje)
Zaimplementuj procedurę sortowania przez selekcje: 
    void SortPrzezSelekcje(int *tab, int i1, int i2)
    {
      // sortuje elementy tablicy tab (tylko z zakresu i1,i2)
    }
Sortowanie przez selekcję polega na tym, że znajdujemy największy element w ciągu i zamieniamy go z ostatnim elementem, następnie w ciągu bez ostatniego elementu znajdujemy największy element i zamieniamy go z ostatnim, itd. 
    1    5    15    95    7    3    84    85    86
                    ^                           ^
                    |                           |
                    -----------------------------

    1    5    15    86    7    3    84    85    95

    1    5    15    86    7    3    84    85
                    ^                     ^
                    |                     |
                    -----------------------

    1    5    15    85    7    3    84    86

    1    5    15    85    7    3    84

    (i tak dalej ...)
Zbadaj czas działania tej procedury, podobnie jak w zadaniu 1. Porównaj oba algorytmy, tj zestaw czasy działania obu procedur na tych samych danych.
 
 

 

Literatura.

  • Cormen, Leiserson, Rivest "Wprowadzenie do algorytmów"
  • Banachowski, Diks, Rytter "Algorytmy i struktury danych"

    •