Sortowanie c.d.

Zadanie 6
(sortowanie szybkie; QuickSort)
Zaimplementuj procedurę sortującą QuickSort: 
    // język C
    void QuickSort(int *tab, int i1, int i2)
    {
    }

    { język Pascal }
    type t_tablica=array[1..1000] of integer;
    procedure QuickSort(var tab:t_tablica; i1,i2:integer);
    begin
    end;
Procedura QuickSort polega na:
  1. podzieleniu tablicy na dwie części A i B, w taki sposób że wszystkie elementy A sa <= od elementów B, przy pomocy procedury "Podział"
  2. posortowaniu A (rekurencyjne wywołanie QuickSort)
  3. posortowaniu B (rekurencyjne wywołanie QuickSort)
 Procedura "Podział" jest następująca:
  1. niech "x" będzie elementem o indeksie i1
  2. i:=i1-1; j:=i2+1;
  3. przesuwamy indeks "j" w lewo tak długo aż znajdziemy element <=x
  4. przesuwamy indeks "i" w prawo tak długo aż znajdziemy element >=x
  5. jeśli i<j to zamieniamy i-ty i j-ty element tablicy, w przeciwnym wypadku znaleźliśmy podział (są to przedziały: [i1...j] i [j+1...i2])
  6. jeśli nie znaleźliśmy podziału to wracamy do punktu 3
    x:=5 (to nie jest zgodne z pkt 1 ...)

        i1                                    i2 
        |                                     |
        1    3    4    10    5    3    11     7
    ^                                             ^
    i                                         <-- j

        1    3    4    10    5    3    11     7
    ^                             ^
    i                             j

        1    3    4    10    5    3    11     7
    ^                             ^
    i -->                         j

        1    3    4    10    5    3    11     7
                       ^          ^
                       i          j

        1    3    4    3    5    10    11     7
                       ^          ^
                       i          j

    (... i tak dalej)
  • UWAGA: procedura Podzał jest "bardzo trikowa" - musi być zaprogramowana dokładnie tak jak to opisano powyżej.
  • Procedura powinna zliczać operacje porównywania elementów tablicy (w zmiennej Czas). Przypomnijmy że pesymistyczny czas działania QuickSort to O(n^2), jednak jeśli założymy że wszystkie permutacje wejściowego ciągu liczb są równo prawdopodobne to średni czas działania QuickSort wynosi O(n log n).
  • Sprawdź działnie tej procedury na krótkich ciągach liczb.



    • ... kilka bardzo prostych zadan ...


    Zadanie 7

    Mamy tablice jednowymiarowa. Wyznaczyc element MAX i MIN oraz wszystkie pozycje na ktorych wystepuja.

    Zadanie 8
    Mamy tablice jednowymiarowa. Wyznaczyc element ktory najczesciej wystepuje.

    Zadanie 9
    Mamy tablice dwuwymiarowa (macierz). Wyzerowac elementy macierzy lezace na glownej przekatnej oraz jej "dotykajace" (dotykajace przekatnej bokiem a nie rogiem).