12. Třídění

Question 1

Co jsou klíčové principy třídění?

Answer 1

• Stabilita: Třídící algoritmus je stabilní, pokud udržuje relativní pořadí stejných klíčů v seřazeném poli.
• Časová složitost: Měří, jak rychle algoritmus zpracovává data.
• Prostorová složitost: Udává, kolik dodatečné paměti algoritmus vyžaduje.

Question 2

Jak funguje a jaké jsou charakteristiky Bubble Sort?

Answer 2

• Princip: Opakovaně prochází seznam, porovnává sousední prvky a prohazuje je, pokud nejsou ve správném pořadí.
• Stabilita: Stabilní.
• Časová složitost: O(n^2) ve všech případech.

Question 3

Jak funguje a jaké jsou charakteristiky Selection Sort?

Answer 3

• Princip: Hledá nejmenší prvek z neseřazené části a vyměňuje ho s prvním neseřazeným prvkem.
• Stabilita: Nestabilní, ale může být modifikován pro stabilitu.
• Časová složitost: O(n^2) ve všech případech.

Question 4

Jak funguje a jaké jsou charakteristiky Insertion Sort?

Answer 4

• Princip: Vytváří finální seřazený seznam postupným přebíráním každého prvku, hledáním správného místa ve seřazené části a jeho vložením.
• Stabilita: Stabilní.
• Časová složitost: O(n^2) ve nejhorším případě, O(n) pro seřazený vstup.