Sorting - NTIN058

• Title: Třídění
• Guaranteed by: Department of Distributed and Dependable Systems (32-KDSS)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech
• Teaching methods: full-time
• Additional information: http://d3s.mff.cuni.cz/teaching/ntin058
• Guarantor: RNDr. Alena Koubková, CSc.
• Class: Informatika Mgr. - volitelný
• Classification: Informatics > Theoretical Computer Science

Annotation

English

A survey on sorting algorithms and their analysis. Sequential and parallel sorting algorithms, internal and external sorting.

Last update: Zavoral Filip, RNDr., Ph.D. (03.04.2001)

Czech

Přehled známých i méně známých třídicích algoritmů a jejich analýza. Algoritmy pro sekvenční a paralelní třídění, třídění souborů v interní paměti, externí třídění.

Last update: ()

Literature

Akl, S. G.: Parallel sorting algorithms. Academic Press, 1985.

Knuth, D. E.: The art of computer programming. Sorting and searching. Addison-Wesley, 1973.

Sedgewick, R.: Algorithms in C. Addison-Wesley, 1998 (česky SoftPress, 2003).

Last update: Koubková Alena, RNDr., CSc. (27.04.2005)

Requirements to the exam

Zkouška má pouze ústní část. Požadavky odpovídají sylabu přednášky.

Last update: Koubková Alena, RNDr., CSc. (10.10.2017)

Syllabus

English

Sequential algorithms for internal sorting. Algorithms based on comparisons, bucket sorting, estimates of their complexity. A survey on well-known sorting algorithms (Bubblesort, Insertionsort, Quicksort, Mergesort,...) and their modifications. Some little-known sorting algorithms.

Parallel sorting. Parallel models of computation, measures of complexity of parallel algorithms. Special parallel architectures for sorting (sorting networks). Sorting on multi-purpose parallel machines with various types of processor interconnection ( linear, tree, ...), shared memory computers. Synchronous and asynchronous sorting.

Sorting of external files on tapes and discs. Complexity measures for external sorting.

Last update: Koubková Alena, RNDr., CSc. (28.04.2005)

Czech

Sekvenční algoritmy pro vnitřní třídění. Algoritmy založené na porovnávání, přihrádkové třídění, odhady složitosti. Přehled známých třídicích algoritmů (bubblesort, insertsort, quicksort, mergesort, ...) a jejich modifikace. Méně známé třídicí algoritmy (Shellsort, shakersort, hybridsort, ...).

Paralelní třídění. Paralelní modely výpočtu, míry složitosti paralelních algoritmů. Speciální paralelní architektury pro třídění (třídicí sítě). Třídění na víceúčelových paralelních strojích s různými způsoby propojení procesorů (lineární propojení, stromy, ..., sdílená paměť). Synchronní a asynchronní třídění.

Externí třídění souborů uložených na páskách a na discích. Míry složitosti externího třídění.

Last update: Koubková Alena, RNDr., CSc. (28.04.2005)