Droid & Codegen
Codegen Codegen
ΠŸΡ€ΠΈΠ²Π΅Ρ‚, Π”Ρ€ΠΎΠΈΠ΄. Π‘Π»ΡƒΡˆΠ°ΠΉ, я Ρ‚ΡƒΡ‚ ΠΏΠΎΠ΄ΡƒΠΌΠ°Π» ΠΏΡ€ΠΎ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡŽ быстрой сортировки... Π’Ρ‹ Π½Π΅ знаСшь, ΠΌΠΎΠΆΠ΅Ρ‚, Π΅ΡΡ‚ΡŒ ΠΊΠ°ΠΊΠΎΠΉ-Π½ΠΈΠ±ΡƒΠ΄ΡŒ Ρ…ΠΈΡ‚Ρ€Ρ‹ΠΉ Ρ‚Ρ€ΡŽΠΊ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Ρ€Π΅Π°Π»ΡŒΠ½ΠΎ прСвосходит ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ разбиСния для Π±ΠΎΠ»ΡŒΡˆΠΈΡ…, ΠΏΠΎΡ‡Ρ‚ΠΈ отсортированных Π΄Π°Π½Π½Ρ‹Ρ…?
Droid Droid
Π”Ρ€ΠΎΠΈΠ΄: Для Π±ΠΎΠ»ΡŒΡˆΠΈΡ…, ΠΏΠΎΡ‡Ρ‚ΠΈ отсортированных массивов классичСский ΠΏΡ€ΠΈΠ΅ΠΌ – ΡΠΌΠ΅ΡˆΠ°Ρ‚ΡŒ Π±Ρ‹ΡΡ‚Ρ€ΡƒΡŽ сортировку с сортировкой вставками ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠ΅Π΄ΠΈΠ°Π½Ρƒ ΠΈΠ· Ρ‚Ρ€Π΅Ρ… элСмСнтов Π² качСствС ΠΎΠΏΠΎΡ€Π½ΠΎΠ³ΠΎ. Π’Ρ‹Π±ΠΈΡ€Π°ΠΉ ΠΌΠ΅Π΄ΠΈΠ°Π½Ρƒ ΠΈΠ· ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ, срСднСго ΠΈ послСднСго элСмСнтов, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ ΠΏΠ»ΠΎΡ…ΠΈΡ… Ρ€Π°Π·Π΄Π΅Π»Π΅Π½ΠΈΠΉ, Π° ΠΊΠΎΠ³Π΄Π° Ρ€Π°Π·ΠΌΠ΅Ρ€Ρ‹ подмассивов становятся мСньшС, скаТСм, 10 ΠΈΠ»ΠΈ 20, ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΈ Π½Π° сортировку вставками, ΠΎΠ½Π° ΠΎΡ‚Π»ΠΈΡ‡Π½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ с ΠΏΠΎΡ‡Ρ‚ΠΈ отсортированными Π΄Π°Π½Π½Ρ‹ΠΌΠΈ. Π­Ρ‚ΠΎΡ‚ Π³ΠΈΠ±Ρ€ΠΈΠ΄ – часто Π½Π°Π·Ρ‹Π²Π°Π΅ΠΌΡ‹ΠΉ introsort ΠΈΠ»ΠΈ Π³ΠΈΠ±Ρ€ΠΈΠ΄ быстрой сортировки ΠΈ сортировки вставками – ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΡ‚ ΠΎΠ±Ρ‹Ρ‡Π½Ρ‹ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ разбиСния, особСнно Ссли Π΄Π°Π½Π½Ρ‹Π΅ слабо ΠΏΠ΅Ρ€Π΅ΠΌΠ΅ΡˆΠ°Π½Ρ‹. ΠžΠ³Ρ€Π°Π½ΠΈΡ‡ΡŒ Π³Π»ΡƒΠ±ΠΈΠ½Ρƒ рСкурсии – ΠΈ всё Π±ΡƒΠ΄Π΅Ρ‚ Π² порядкС.