Seznámit studenty se základními datovými strukturami a algoritmy.

Požadavky na studenta
Zápočet: Implementace algoritmů třídění
Zkouška: Znalost algoritmů třídění

======Obsah======

  - [[cs>Problém]]y a [[cs>Algoritmus|algoritmy]]. Příklady, základní aspekty.

  - Efektivnost algoritmů. [[cs>Složitost]] algoritmu, big-O notace, úvod do analýzy složitosti algoritmů.

  - Základní datové struktury. Lineární datové struktury ([[cs>Seznam|seznam]], [[cs>Zásobník|zásobník]], [[cs>Fronta|fronta]]). Stromové a nelineární datové struktury.

  - [[cs>Řazení|Třídění]], vymezení problému a přístupy.

  - Metody vnitřního třídění.
    * [[wp>Insertion sort|Třídění vkládáním]] (přímá metoda, třídění s ubývajícím krokem),
    * třídění výměnou ([[wp>Bubble sort|bublinkové třídění]] a jeho varianty,
    * třídění [[cs>Quicksort]]),
    * [[wp>Selection sort|třídění výběrem]] (přímá metoda, [[wp>Heapsort|třídění haldou]]). Implementace jednotlivých metod.

  - Další metody třídění. [[cs>Bucket Sort|Přihrádkové třídění]]. [[cs>Radix sort|Číslicové třídění]].

  - Vnější třídění. Metoda slučování. Polyfázové třídění.

  - Pořádkové statistiky.

======Literatura======
  * WIRTH, N. Algoritmy a štruktúry údajov. Alfa, 1989.
  * SEDGEWICK, R. Algoritmy v C, části 1- 4: základy, datové struktury, třídění, vyhledávání. Praha, Softpress, 2003. [[isbn>80-86497-56-9]]
  * CORMEN, T. H., LEISERSON C. E., RIVEST D. L., STEIN C. Introduction to Algorithms, Second Edition. MIT Press, 2001. [[isbn>0-07-013151-1]]
  * KNUTH, D. The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley, 2005. [[isbn>0-201-89685-0]]

<code pli>
procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure
</code>