Laboratorium 2

Badanie złożoności algorytmów na przykładzie algorytmów sortowania

    W czasie tego ćwiczenia studenci zapoznają się z praktyczną implementacją wybranych algorytmów sortowania. W przykładowym programie zaimplementowano następujące algorytmy sortowania: Ponadto stworzono interfejsy, pozwalające na implementację następujących algorytmów sortowania:
W czasie ćwiczenia wybrane algorytmy zostaną przebadane pod kątem złożoności obliczeniowej, stabilności oraz wykorzystania stosu systemowego (w przypadku algorytmów rekurencyjnych). Zbadany zostanie również wpływ początkowego uporządkowania zbioru oraz powtarzanie się kluczy. W przypadku algorytmu Shella zbadany zostanie również wpływ ciągu sterującego. W ramach ćwiczenia studenci będą mieli również możliwość eksperymentowania implementacją algorytmów sortowania bąbelkowego, przez scalanie czy zliczanie.

Uwagi

Przed przystąpieniem do ćwiczenia należy obowiązkowo zapoznać się z instrukcją do ćwiczenia i kodami źródłowymi. Przed przystąpieniem do pisania sprawozdania należy się zapoznać z informacjami dodatkowymi.

Literatura

  • R. Sedgewick "Algorytmy w C++", Wydawnictwo RM, 1999.
  • R. Sedgewick, K. Wayne "Algorytmy", Wydawnictwo Helion, 2012.
  • A. Drozdek "C++ algorytmy i struktury danych", Wydawnictwo Helion, 2004.
  • J. Grębosz "Symfonia C++" Wydawnictwo Oficyna Kallimach 1997.
  • J. Grębosz "Pasja C++" Wydawnictwo Oficyna Kallimach 1997.
    Instrukcja do ćwiczenia
    Źródła
    Wyślij sprawozdanie: