πŸ“Š Алгоритми Бортування

Big O Complexity

Π£ Computer Science ΠΌΠΈ міряємо ΡˆΠ²ΠΈΠ΄ΠΊΡ–ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ Π½Π΅ сСкундами, Π° ΠΊΡ–Π»ΡŒΠΊΡ–ΡΡ‚ΡŽ ΠΎΠΏΠ΅Ρ€Π°Ρ†Ρ–ΠΉ відносно N (ΠΊΡ–Π»ΡŒΠΊΡ–ΡΡ‚ΡŒ Π΅Π»Π΅ΠΌΠ΅Π½Ρ‚Ρ–Π²).

  • Bubble Sort (O(NΒ²)): "Π‘ΠΏΠ»ΠΈΠ²Π°Ρ”" Π±ΡƒΠ»ΡŒΠ±Π°ΡˆΠΊΠ°. ΠŸΡ€ΠΎΡΡ‚ΠΈΠΉ, Π°Π»Π΅ Π½Π°ΠΉΠΏΠΎΠ²Ρ–Π»ΡŒΠ½Ρ–ΡˆΠΈΠΉ.
  • Selection Sort (O(NΒ²)): Π‘ΠΊΠ°Π½ΡƒΡ” вСсь список, Ρ‰ΠΎΠ± Π·Π½Π°ΠΉΡ‚ΠΈ 1 ΠΌΡ–Π½Ρ–ΠΌΡƒΠΌ. Π ΠΎΠ±ΠΈΡ‚ΡŒ ΠΌΠ°Π»ΠΎ записів (swaps), Π°Π»Π΅ Π±Π°Π³Π°Ρ‚ΠΎ Ρ‡ΠΈΡ‚Π°Π½ΡŒ.
  • Quick Sort (O(N log N)): РСкурсивно Π΄Ρ–Π»ΠΈΡ‚ΡŒ масив. Найшвидший Π½Π° ΠΏΡ€Π°ΠΊΡ‚ΠΈΡ†Ρ–, Π°Π»Π΅ Π½Π΅ "ΡΡ‚Π°Π±Ρ–Π»ΡŒΠ½ΠΈΠΉ" (ΠΌΠΎΠΆΠ΅ міняти місцями ΠΎΠ΄Π½Π°ΠΊΠΎΠ²Ρ– числа).