Π§ΡΠΎ ΡΠ°ΠΊΠΎΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΡΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΡΡ [data sorting, ordering] β ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΡΡΠ°ΠΏΠΎΠ² ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠΈ Π΄Π°Π½Π½ΡΡ , ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ Π΄Π°Π½Π½ΡΡ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΠΌΠΎΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΏΡΠΈΠ·Π½Π°ΠΊΠΎΠ², Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΡ ΠΊΠ»ΡΡΠ°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π·Π°ΠΏΠΈΡΠ΅ΠΉ ΡΠΎΡΡΠΈΡΡΠ΅ΠΌΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° Π΄Π°Π½Π½ΡΡ ΠΏΠΎ Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π½ΠΈΡ ΠΈΠ»ΠΈ ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ Π²Π΅Π»ΠΈΡΠΈΠ½, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΡ ΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² Π΄Π°Π½Π½ΡΡ ΡΡΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎ ΡΡΠΊΠΎΡΡΠ΅Ρ ΠΈΡ Π΄Π°Π»ΡΠ½Π΅ΠΉΡΡΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΡ.
Π‘ΠΌΠΎΡΡΠ΅ΡΡ ΡΡΠΎ ΡΠ°ΠΊΠΎΠ΅ «Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΡΡ » Π² Π΄ΡΡΠ³ΠΈΡ ΡΠ»ΠΎΠ²Π°ΡΡΡ :
Π‘ΠΠ Π’ΠΠ ΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΡΡ β ΡΠ». ΡΠΎΡΠΌΠ°ΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π²ΠΈΠ½ΡΠ° (ΡΡΡΠ».) β¦ Hacker’s dictionary
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ β Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ ΠΏΡΠΎΡΡΠΎΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. Π₯ΠΎΡΡ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΡΡΡΠΏΠ°Π΅Ρ Π² ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΠΈ Π±ΠΎΠ»Π΅Π΅ ΡΠ»ΠΎΠΆΠ½ΡΠΌ (ΡΠ°ΠΊΠΈΠΌ ΠΊΠ°ΠΊ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°), Ρ Π½Π΅Π³ΠΎ Π΅ΡΡΡ ΡΡΠ΄ ΠΏΡΠ΅ΠΈΠΌΡΡΠ΅ΡΡΠ²: ΡΡΡΠ΅ΠΊΡΠΈΠ²Π΅Π½ Π½Π° Π½Π΅Π±ΠΎΠ»ΡΡΠΈΡ Π½Π°Π±ΠΎΡΠ°Ρ Π΄Π°Π½Π½ΡΡ , Π½Π° Π½Π°Π±ΠΎΡΠ°Ρ Π΄Π°Π½Π½ΡΡ Π΄ΠΎ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π° β (Π°Π½Π³Π». Shell sort) Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΡΠ²Π»ΡΡΡΠΈΠΉΡΡ ΡΡΠΎΠ²Π΅ΡΡΠ΅Π½ΡΡΠ²ΠΎΠ²Π°Π½Π½ΡΠΌ Π²Π°ΡΠΈΠ°Π½ΡΠΎΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ. ΠΠ΄Π΅Ρ ΠΌΠ΅ΡΠΎΠ΄Π° Π¨Π΅Π»Π»Π° ΡΠΎΡΡΠΎΠΈΡ Π² ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΡΡΠΎΡΡΠΈΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΡΠ΄ΠΎΠΌ, Π½ΠΎ ΠΈ Π½Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ½Π½ΠΎΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΈ Π΄ΡΡΠ³ ΠΎΡ Π΄ΡΡΠ³Π°. ΠΠ½ΡΠΌΠΈβ¦ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ β (Selection sort) Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ ΠΈ ΠΊΠ°ΠΊ ΡΡΡΠΎΠΉΡΠΈΠ²ΡΠΉ ΠΈ ΠΊΠ°ΠΊ Π½Π΅ΡΡΡΠΎΠΉΡΠΈΠ²ΡΠΉ. ΠΠ° ΠΌΠ°ΡΡΠΈΠ²Π΅ ΠΈΠ· n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈΠΌΠ΅Π΅Ρ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ Π² Ρ ΡΠ΄ΡΠ΅ΠΌ, ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Ξ(n2), ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Ρ ΡΡΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ Π΄Π΅Π»Π°ΡΡΡΡ Π·Π° ΠΏΠΎΡΡΠΎΡΠ½Π½ΠΎΠ΅β¦ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠΎΠ΄ΡΡΡΡΠΎΠΌ β Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π΄ΠΈΠ°ΠΏΠ°Π·ΠΎΠ½ ΡΠΈΡΠ΅Π» ΡΠΎΡΡΠΈΡΡΠ΅ΠΌΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° (ΡΠΏΠΈΡΠΊΠ°) Π΄Π»Ρ ΠΏΠΎΠ΄ΡΡΡΡΠ° ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΠΎΠ΄ΡΡΡΡΠΎΠΌ ΡΠ΅Π»Π΅ΡΠΎΠΎΠ±ΡΠ°Π·Π½ΠΎ Π»ΠΈΡΡ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΡΠΎΡΡΠΈΡΡΠ΅ΠΌΡΠ΅ ΡΠΈΡΠ»Π° ΠΈΠΌΠ΅ΡΡ (ΠΈΠ»ΠΈ ΠΈΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠΎΠ±ΡΠ°Π·ΠΈΡΡ Π²)β¦ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° β 4.1.10 ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° (sorting): ΠΠ΅ΠΉΡΡΠ²ΠΈΡ ΠΏΠΎ ΡΠ°Π·Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΠ²Π΅ΡΠ΄ΡΡ ΠΎΡΡ ΠΎΠ΄ΠΎΠ² Π½Π° ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠ΅ ΠΊΠ°ΡΠ΅Π³ΠΎΡΠΈΠΈ ΠΈΠ»ΠΈ ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ ΠΈΡ ΡΠΌΠ΅ΡΠΈΠ²Π°Π½ΠΈΡ. ΠΡΡΠΎΡΠ½ΠΈΠΊ: ΠΠΠ‘Π’ Π 54235 2010: Π’ΠΎΠΏΠ»ΠΈΠ²ΠΎ ΡΠ²Π΅ΡΠ΄ΠΎΠ΅ ΠΈΠ· Π±ΡΡΠΎΠ²ΡΡ ΠΎΡΡ ΠΎΠ΄ΠΎΠ². Π’Π΅ΡΠΌΠΈΠ½Ρ ΠΈ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΠΎΡΠΈΠ³ΠΈΠ½Π°Π» Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ° β¦ Π‘Π»ΠΎΠ²Π°ΡΡ-ΡΠΏΡΠ°Π²ΠΎΡΠ½ΠΈΠΊ ΡΠ΅ΡΠΌΠΈΠ½ΠΎΠ² Π½ΠΎΡΠΌΠ°ΡΠΈΠ²Π½ΠΎ-ΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠΎΠΉ Π΄ΠΎΠΊΡΠΌΠ΅Π½ΡΠ°ΡΠΈΠΈ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ β ΠΠ΅ΠΉΡΡΠ²ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π° ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ ΡΠΎΡΠ΅ΠΊ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ (Π°Π½Π³Π». merge sort) Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΊΠΎΡΠΎΡΡΠΉ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠΈΠ²Π°Π΅Ρ ΡΠΏΠΈΡΠΊΠΈ (ΠΈΠ»ΠΈ Π΄ΡΡΠ³ΠΈΠ΅ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ , Π΄ΠΎΡΡΡΠΏ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ ΠΊΠΎΡΠΎΡΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π΄Π²ΠΎΠΈΡΠ½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° β ΠΡΠΈΠΌΠ΅Ρ Π΄Π²ΠΎΠΈΡΠ½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π΄Π²ΠΎΠΈΡΠ½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° (ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π²ΠΎΠΈΡΠ½ΡΠΌ Π΄Π΅ΡΠ΅Π²ΠΎΠΌ, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ, Π΄ΡΠ΅Π²Π΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Ρ ΠΏΠΎΠΌΠΎΡΡΡ Π±ΠΈΠ½Π°ΡΠ½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°, Π°Π½Π³Π». β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΌΠ΅Π΄ΠΈΡΠΈΠ½ΡΠΊΠ°Ρ β I Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΌΠ΅Π΄ΠΈΡΠΈΠ½ΡΠΊΠ°Ρ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΏΠΎΡΠ°ΠΆΠ΅Π½Π½ΡΡ ΠΈ Π±ΠΎΠ»ΡΠ½ΡΡ ΠΏΡΠΈ ΠΈΡ ΠΏΠΎΡΡΡΠΏΠ»Π΅Π½ΠΈΠΈ Π½Π° ΡΡΠ°ΠΏΡ ΠΌΠ΅Π΄ΠΈΡΠΈΠ½ΡΠΊΠΎΠΉ ΡΠ²Π°ΠΊΡΠ°ΡΠΈΠΈ ΠΈΠ»ΠΈ Π² Π»Π΅ΡΠ΅Π±Π½ΡΠ΅ ΡΡΡΠ΅ΠΆΠ΄Π΅Π½ΠΈΡ Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ Ρ Π°ΡΠ°ΠΊΡΠ΅ΡΠ° ΠΈ ΡΡΠΆΠ΅ΡΡΠΈ ΠΏΠΎΡΠ°ΠΆΠ΅Π½ΠΈΡ (Π·Π°Π±ΠΎΠ»Π΅Π²Π°Π½ΠΈΡ) Π½Π° Π³ΡΡΠΏΠΏΡ Π½ΡΠΆΠ΄Π°ΡΡΠΈΡ ΡΡ Π² ΠΎΠ΄Π½ΠΎΡΠΎΠ΄Π½ΡΡ Π»Π΅ΡΠ΅Π±Π½ΠΎβ¦ β¦ ΠΠ΅Π΄ΠΈΡΠΈΠ½ΡΠΊΠ°Ρ ΡΠ½ΡΠΈΠΊΠ»ΠΎΠΏΠ΅Π΄ΠΈΡ
ΠΠ½Π΅ΡΠ½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° β ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π°Π½Π½ΡΡ , ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½Π½ΡΡ Π½Π° ΠΏΠ΅ΡΠΈΡΠ΅ΡΠΈΠΉΠ½ΡΡ ΡΡΡΡΠΎΠΉΡΡΠ²Π°Ρ ΠΈ Π½Π΅ Π²ΠΌΠ΅ΡΠ°ΡΡΠΈΡ ΡΡ Π² ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠ²Π½ΡΡ ΠΏΠ°ΠΌΡΡΡ, ΡΠΎ Π΅ΡΡΡ ΠΊΠΎΠ³Π΄Π° ΠΏΡΠΈΠΌΠ΅Π½ΠΈΡΡ ΠΎΠ΄Π½Ρ ΠΈΠ· Π²Π½ΡΡΡΠ΅Π½Π½ΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ. Π‘ΡΠΎΠΈΡ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π²Π½ΡΡΡΠ΅Π½Π½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½Π΅ΠΉ Π²Π½Π΅ΡΠ½Π΅ΠΉ, ΡΠ°ΠΊβ¦ β¦ ΠΠΈΠΊΠΈΠΏΠ΅Π΄ΠΈΡ
ΠΡΠ½ΠΎΠ²Π½ΡΠ΅ Π²ΠΈΠ΄Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ ΠΈ ΠΏΡΠΈΠΌΠ΅ΡΡ ΠΈΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ
ΠΠ°ΠΌΡΡΠΊΠ° Π΄Π»Ρ ΡΠ΅Ρ , ΠΊΡΠΎ Π³ΠΎΡΠΎΠ²ΠΈΡΡΡ ΠΊ ΡΠΎΠ±Π΅ΡΠ΅Π΄ΠΎΠ²Π°Π½ΠΈΡ Π½Π° ΠΏΠΎΠ·ΠΈΡΠΈΡ ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠ°
ΠΠ° ΡΠΎΠ±Π΅ΡΠ΅Π΄ΠΎΠ²Π°Π½ΠΈΡΡ Π±ΡΠ΄ΡΡΠΈΠΌ ΡΡΠ°ΠΆΡΡΠ°ΠΌ-ΡΠ°Π·ΡΠ°Π±ΠΎΡΡΠΈΠΊΠ°ΠΌ Π΄Π°ΡΡ Π·Π°Π΄Π°Π½ΠΈΡ Π½Π° Π·Π½Π°Π½ΠΈΠ΅ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² β Π² ΡΠΎΠΌ ΡΠΈΡΠ»Π΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ. ΠΠΊΠ°Π΄Π΅ΠΌΠΈΡ Π―Π½Π΄Π΅ΠΊΡΠ° ΠΈ ΡΠΎΠ°Π²ΡΠΎΡ ΡΠΏΠ΅ΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ Β«ΠΡΠΊΡΡΡΡΠ²ΠΎ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ Π½Π° ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΌ C++Β» ΠΠ»ΡΡ Π¨ΠΈΡΠΊΠΎΠ² ΡΠΎΡΡΠ°Π²ΠΈΠ»ΠΈ ΡΠΏΠΈΡΠΎΠΊ Π΄Π»Ρ ΠΏΠΎΠ΄Π³ΠΎΡΠΎΠ²ΠΊΠΈ Ρ ΠΌΠ΅ΡΠΎΠ΄Π°ΠΌΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΏΡΠΈΠΌΠ΅ΡΠ°ΠΌΠΈ ΠΈΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈ Π³ΠΈΡΠΊΠ°ΠΌΠΈ, ΡΡΠΎΠ±Ρ Π»ΡΡΡΠ΅ ΠΏΠΎΠ½ΡΡΡ, ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ ΡΠ°Π±ΠΎΡΠ°ΡΡ.
ΠΡΠ·ΡΡΡΠΊΠΎΠ²Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΈ Π΅Ρ ΡΠ»ΡΡΡΠ΅Π½ΠΈΡ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ β ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΡΠ°ΠΌΡΡ ΠΈΠ·Π²Π΅ΡΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ΄Π΅ΡΡ Π½ΡΠΆΠ½ΠΎ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΡΠΎΡΠ΅Π΄Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈ ΠΌΠ΅Π½ΡΡΡ ΡΠΈΡΠ»Π° ΠΌΠ΅ΡΡΠ°ΠΌΠΈ, Π΅ΡΠ»ΠΈ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅Π΅ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ Π±ΠΎΠ»ΡΡΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Ρ Π±ΠΎΠ»ΡΡΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ ΠΎΠΊΠ°Π·ΡΠ²Π°ΡΡΡΡ Π² ΠΊΠΎΠ½ΡΠ΅ ΡΠΏΠΈΡΠΊΠ°, Π° Ρ ΠΌΠ΅Π½ΡΡΠΈΠΌΠΈ ΠΎΡΡΠ°ΡΡΡΡ Π² Π½Π°ΡΠ°Π»Π΅.
ΠΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΡΠΈΡΠ°Π΅ΡΡΡ ΡΡΠ΅Π±Π½ΡΠΌ ΠΈ ΠΏΠΎΡΡΠΈ Π½Π΅ ΠΏΡΠΈΠΌΠ΅Π½ΡΠ΅ΡΡΡ Π½Π° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅ ΠΈΠ·-Π·Π° Π½ΠΈΠ·ΠΊΠΎΠΉ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΡΡΠΈ: ΠΎΠ½ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π° ΡΠ΅ΡΡΠ°Ρ , Π² ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ°Π»Π΅Π½ΡΠΊΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ (ΠΈΡ Π½Π°Π·ΡΠ²Π°ΡΡ Β«ΡΠ΅ΡΠ΅ΠΏΠ°Ρ Π°ΠΌΠΈΒ») ΡΡΠΎΡΡ Π² ΠΊΠΎΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠ΄Π½Π°ΠΊΠΎ Π½Π° Π½ΡΠΌ ΠΎΡΠ½ΠΎΠ²Π°Π½Ρ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ Π΄ΡΡΠ³ΠΈΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠ΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°ΡΡΡΡΠΊΠΎΠΉ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠΈΠ²Π°Π½ΠΈΠ΅ΠΌ (ΡΠ΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°)
Π¨Π΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΎΡΠ»ΠΈΡΠ°Π΅ΡΡΡ ΠΎΡ ΠΏΡΠ·ΡΡΡΠΊΠΎΠ²ΠΎΠΉ ΡΠ΅ΠΌ, ΡΡΠΎ ΠΎΠ½Π° Π΄Π²ΡΠ½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½Π°Ρ: Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°Π΅ΡΡΡ Π½Π΅ ΡΡΡΠΎΠ³ΠΎ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ, Π° ΡΠ½Π°ΡΠ°Π»Π° ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ, Π·Π°ΡΠ΅ΠΌ ΡΠΏΡΠ°Π²Π° Π½Π°Π»Π΅Π²ΠΎ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°ΡΡΡΡΠΊΠΎΠΉ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°ΡΡΡΡΠΊΠΎΠΉ β ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ. ΠΡ ΠΈΠ΄Π΅Ρ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ Β«ΡΡΡΡΠ°Π½ΠΈΡΡΒ» ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Ρ Π½Π΅Π±ΠΎΠ»ΡΡΠΈΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π² ΠΊΠΎΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°, ΠΊΠΎΡΠΎΡΡΠ΅ Π·Π°ΠΌΠ΅Π΄Π»ΡΡΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°. ΠΡΠ»ΠΈ ΠΏΡΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠ²ΠΎΠΉ ΠΈ ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°Ρ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅Π±ΠΎΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π° ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ ΡΠΎΡΠ΅Π΄Π½ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΠΎ ΠΏΡΠΈ Β«ΡΠ°ΡΡΡΡΡΠ²Π°Π½ΠΈΠΈΒ» ΡΠ½Π°ΡΠ°Π»Π° Π±Π΅ΡΡΡΡΡ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ Π±ΠΎΠ»ΡΡΠΎΠ΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΡΡΠ°Π²Π½ΠΈΠ²Π°Π΅ΠΌΡΠΌΠΈ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌΠΈ, Π° ΠΏΠΎΡΠΎΠΌ ΠΎΠ½ΠΎ ΡΡΠΆΠ°Π΅ΡΡΡ Π²ΠΏΠ»ΠΎΡΡ Π΄ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ.
ΠΠ΅ΡΠ²ΠΎΠ½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΡΠ°Π·ΡΡΠ² Π½ΡΠΆΠ½ΠΎ Π²ΡΠ±ΠΈΡΠ°ΡΡ Π½Π΅ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π° Ρ ΡΡΡΡΠΎΠΌ ΡΠΏΠ΅ΡΠΈΠ°Π»ΡΠ½ΠΎΠΉ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ β ΡΠ°ΠΊΡΠΎΡΠ° ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΡ, ΠΎΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠ°Π²Π½ΠΎ 1,247. Π‘Π½Π°ΡΠ°Π»Π° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½ΡΡΡΡΡ ΡΠ°Π·ΠΌΠ΅ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°, ΠΏΠΎΠ΄Π΅Π»ΡΠ½Π½ΠΎΠΌΡ Π½Π° 1,247; Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ ΡΠ°Π³Π΅ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ Π±ΡΠ΄Π΅Ρ ΡΠ½ΠΎΠ²Π° Π΄Π΅Π»ΠΈΡΡΡΡ Π½Π° ΡΠ°ΠΊΡΠΎΡ ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΡ β ΠΈ ΡΠ°ΠΊ Π΄ΠΎ ΠΎΠΊΠΎΠ½ΡΠ°Π½ΠΈΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
ΠΡΠΎΡΡΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ
ΠΡΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ ΠΌΠ°ΡΡΠΈΠ² ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ ΠΏΠ΅ΡΠ΅Π±ΠΈΡΠ°Π΅ΡΡΡ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ. ΠΡΠΈ ΡΡΠΎΠΌ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΡΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΡΠ°Π·ΠΌΠ΅ΡΠ°Π΅ΡΡΡ ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΠΎΠ½ ΠΎΠΊΠ°Π·Π°Π»ΡΡ ΠΌΠ΅ΠΆΠ΄Ρ Π±Π»ΠΈΠΆΠ°ΠΉΡΠΈΠΌΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ
Π‘Π½Π°ΡΠ°Π»Π° Π½ΡΠΆΠ½ΠΎ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅ΡΡ ΠΏΠΎΠ΄ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° ΠΈ Π½Π°ΠΉΡΠΈ Π² Π½ΡΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌ (ΠΈΠ»ΠΈ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ). ΠΠ°ΡΠ΅ΠΌ Π²ΡΠ±ΡΠ°Π½Π½ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΡΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ Π½Π΅ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. ΠΡΠΎΡ ΡΠ°Π³ Π½ΡΠΆΠ½ΠΎ ΠΏΠΎΠ²ΡΠΎΡΡΡΡ Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π½Π΅ Π·Π°ΠΊΠΎΠ½ΡΠ°ΡΡΡ Π½Π΅ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠ΅ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Ρ.
ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°
ΠΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΡΡΡΡ ΡΠ°Π³ΠΎΠ². Π‘Π½Π°ΡΠ°Π»Π° ΠΈΠ· ΠΌΠ°ΡΡΠΈΠ²Π° Π½ΡΠΆΠ½ΠΎ Π²ΡΠ±ΡΠ°ΡΡ ΠΎΠ΄ΠΈΠ½ ΡΠ»Π΅ΠΌΠ΅Π½Ρ β Π΅Π³ΠΎ ΠΎΠ±ΡΡΠ½ΠΎ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΎΠΏΠΎΡΠ½ΡΠΌ. ΠΠ°ΡΠ΅ΠΌ Π΄ΡΡΠ³ΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»ΡΡΡ ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ΅Π½ΡΡΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΠΎΠΊΠ°Π·Π°Π»ΠΈΡΡ Π΄ΠΎ Π½Π΅Π³ΠΎ, Π° Π±ΠΎΠ»ΡΡΠΈΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π½ΡΠ΅ β ΠΏΠΎΡΠ»Π΅. Π Π΄Π°Π»ΡΡΠ΅ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΡΡΡ ΠΏΠ΅ΡΠ²ΡΠ΅ Π΄Π²Π° ΡΠ°Π³Π° ΠΊ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π°ΠΌ ΡΠΏΡΠ°Π²Π° ΠΈ ΡΠ»Π΅Π²Π° ΠΎΡ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ.
ΠΡΡΡΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΈΠ·ΠΎΠ±ΡΠ΅Π»ΠΈ Π² 1960 Π³ΠΎΠ΄Ρ Π΄Π»Ρ ΠΌΠ°ΡΠΈΠ½Π½ΠΎΠ³ΠΎ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄Π°: ΡΠΎΠ³Π΄Π° ΡΠ»ΠΎΠ²Π°ΡΠΈ Ρ ΡΠ°Π½ΠΈΠ»ΠΈΡΡ Π½Π° ΠΌΠ°Π³Π½ΠΈΡΠ½ΡΡ Π»Π΅Π½ΡΠ°Ρ , Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΎΠ² ΠΎΠ±ΡΠ°Π±Π°ΡΡΠ²Π°Π΅ΠΌΠΎΠ³ΠΎ ΡΠ΅ΠΊΡΡΠ° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ»Π° ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΠ΄Ρ Π·Π° ΠΎΠ΄ΠΈΠ½ ΠΏΡΠΎΠ³ΠΎΠ½ Π»Π΅Π½ΡΡ, Π±Π΅Π· ΠΏΠ΅ΡΠ΅ΠΌΠΎΡΠΊΠΈ Π½Π°Π·Π°Π΄.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ ΠΏΡΠΈΠ³ΠΎΠ΄ΠΈΡΡΡ Π΄Π»Ρ ΡΠ°ΠΊΠΈΡ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ , Π² ΠΊΠΎΡΠΎΡΡΡ Π΄ΠΎΡΡΡΠΏ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ ΠΎΡΡΡΠ΅ΡΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π΄Π»Ρ ΠΏΠΎΡΠΎΠΊΠΎΠ²). ΠΠ΄Π΅ΡΡ ΠΌΠ°ΡΡΠΈΠ² ΡΠ°Π·Π±ΠΈΠ²Π°Π΅ΡΡΡ Π½Π° Π΄Π²Π΅ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ ΡΠ°Π²Π½ΡΠ΅ ΡΠ°ΡΡΠΈ ΠΈ ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΈΠ· Π½ΠΈΡ ΡΠΎΡΡΠΈΡΡΠ΅ΡΡΡ ΠΏΠΎ ΠΎΡΠ΄Π΅Π»ΡΠ½ΠΎΡΡΠΈ. ΠΠ°ΡΠ΅ΠΌ Π΄Π²Π° ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π° ΡΠ»ΠΈΠ²Π°ΡΡΡΡ Π² ΠΎΠ΄ΠΈΠ½.
ΠΠΈΡΠ°ΠΌΠΈΠ΄Π°Π»ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°
ΠΡΠΈ ΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ ΡΠ½Π°ΡΠ°Π»Π° ΡΡΡΠΎΠΈΡΡΡ ΠΏΠΈΡΠ°ΠΌΠΈΠ΄Π° ΠΈΠ· ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠΈΡΠ°ΠΌΠΈΠ΄Π° (ΠΈΠ»ΠΈ Π΄Π²ΠΎΠΈΡΠ½Π°Ρ ΠΊΡΡΠ°) β ΡΡΠΎ ΡΠΏΠΎΡΠΎΠ± ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΏΡΠΈ ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΎΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ·Π»Π° ΠΌΠΎΠΆΠ΅Ρ ΠΎΡΡ ΠΎΠ΄ΠΈΡΡ Π½Π΅ Π±ΠΎΠ»ΡΡΠ΅ Π΄Π²ΡΡ ΠΎΡΠ²Π΅ΡΠ²Π»Π΅Π½ΠΈΠΉ. Π Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π² ΡΠΎΠ΄ΠΈΡΠ΅Π»ΡΡΠΊΠΎΠΌ ΡΠ·Π»Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ Π±ΠΎΠ»ΡΡΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ Π² Π΅Π³ΠΎ Π΄Π²ΡΡ Π΄ΠΎΡΠ΅ΡΠ½ΠΈΡ ΡΠ·Π»Π°Ρ .
ΠΠΈΡΠ°ΠΌΠΈΠ΄Π°Π»ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠΎΡ ΠΎΠΆΠ° Π½Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΠ±ΠΎΡΠΎΠΌ, Π³Π΄Π΅ ΠΌΡ ΡΠ½Π°ΡΠ°Π»Π° ΠΈΡΠ΅ΠΌ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π° Π·Π°ΡΠ΅ΠΌ ΠΏΠΎΠΌΠ΅ΡΠ°Π΅ΠΌ Π΅Π³ΠΎ Π² ΠΊΠΎΠ½Π΅Ρ. ΠΠ°Π»ΡΡΠ΅ Π½ΡΠΆΠ½ΠΎ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΏΠΎΠ²ΡΠΎΡΡΡΡ ΡΡ ΠΆΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ Π΄Π»Ρ ΠΎΡΡΠ°Π²ΡΠΈΡ ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
ΠΠΏΠΈΡΠ°Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΈ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ
ΠΡΡΡΠΏΠ»Π΅Π½ΠΈΠ΅
ΠΠ° ΡΡΡ ΡΠ΅ΠΌΡ Π½Π°ΠΏΠΈΡΠ°Π½ΠΎ ΡΠΆΠ΅ Π½Π΅ΠΌΠ°Π»ΠΎ ΡΡΠ°ΡΠ΅ΠΉ. ΠΠ΄Π½Π°ΠΊΠΎ Ρ Π΅ΡΠ΅ Π½Π΅ Π²ΠΈΠ΄Π΅Π» ΡΡΠ°ΡΡΠΈ, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΡΠ°Π²Π½ΠΈΠ²Π°ΡΡΡΡ Π²ΡΠ΅ ΠΎΡΠ½ΠΎΠ²Π½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π½Π° Π±ΠΎΠ»ΡΡΠΎΠΌ ΡΠΈΡΠ»Π΅ ΡΠ΅ΡΡΠΎΠ² ΡΠ°Π·Π½ΠΎΠ³ΠΎ ΡΠΈΠΏΠ° ΠΈ ΡΠ°Π·ΠΌΠ΅ΡΠ°. ΠΡΠΎΠΌΠ΅ ΡΠΎΠ³ΠΎ, Π΄Π°Π»Π΅ΠΊΠΎ Π½Π΅ Π²Π΅Π·Π΄Π΅ Π²ΡΠ»ΠΎΠΆΠ΅Π½Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ Π½Π°Π±ΠΎΡΠ° ΡΠ΅ΡΡΠΎΠ². ΠΡΠΎ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΡΠΎΠΌΡ, ΡΡΠΎ ΠΌΠΎΠ³ΡΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΡΡΡ ΡΠΎΠΌΠ½Π΅Π½ΠΈΡ Π² ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΡΡΠΈ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΡ. ΠΠ΄Π½Π°ΠΊΠΎ ΡΠ΅Π»Ρ ΠΌΠΎΠ΅ΠΉ ΡΠ°Π±ΠΎΡΡ ΡΠΎΡΡΠΎΠΈΡ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ, ΠΊΠ°ΠΊΠΈΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π±ΡΡΡΡΠ΅Π΅ Π²ΡΠ΅Π³ΠΎ (Π² ΡΠ΅Π»ΠΎΠΌ ΡΡΠΎ ΠΈ ΡΠ°ΠΊ ΠΈΠ·Π²Π΅ΡΡΠ½ΠΎ). Π ΠΏΠ΅ΡΠ²ΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ ΠΌΠ½Π΅ Π±ΡΠ»ΠΎ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΠΎ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ, ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°ΡΡ ΠΈΡ , ΡΡΠΎΠ±Ρ ΠΎΠ½ΠΈ ΡΠ°Π±ΠΎΡΠ°Π»ΠΈ ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π±ΡΡΡΡΠ΅Π΅. Π Π°Π±ΠΎΡΠ°Ρ Π½Π°Π΄ ΡΡΠΈΠΌ, ΠΌΠ½Π΅ ΡΠ΄Π°Π»ΠΎΡΡ ΠΏΡΠΈΠ΄ΡΠΌΠ°ΡΡ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΡ ΡΠΎΡΠΌΡΠ»Ρ Π΄Π»Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π¨Π΅Π»Π»Π°.
ΠΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΌ ΡΡΠ°ΡΡΡ ΠΏΠΎΡΠ²ΡΡΠ΅Π½Π° ΡΠΎΠΌΡ, ΠΊΠ°ΠΊ Π½Π°ΠΏΠΈΡΠ°ΡΡ Π²ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΠΏΡΠΎΡΠ΅ΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΈΡ . ΠΡΠ»ΠΈ Π³ΠΎΠ²ΠΎΡΠΈΡΡ ΠΎ ΡΠ°ΠΌΠΎΠΌ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, ΡΠΎ ΠΈΠ½ΠΎΠ³Π΄Π° ΠΌΠΎΠ³ΡΡ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΡΡΡ ΡΠΎΠ²Π΅ΡΡΠ΅Π½Π½ΠΎ Π½Π΅ΠΎΠΆΠΈΠ΄Π°Π½Π½ΡΠ΅ ΡΡΡΠ΄Π½ΠΎΡΡΠΈ (Π²ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΌ Π±Π»Π°Π³ΠΎΠ΄Π°ΡΡ ΠΎΠΏΡΠΈΠΌΠΈΠ·Π°ΡΠΎΡΡ C++). ΠΠ΄Π½Π°ΠΊΠΎ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅ ΡΡΡΠ΄Π½ΠΎ ΡΠ΅ΡΠΈΡΡ, ΠΊΠ°ΠΊΠΈΠ΅ ΠΈΠΌΠ΅Π½Π½ΠΎ ΡΠ΅ΡΡΡ ΠΈ Π² ΠΊΠ°ΠΊΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π°Ρ Π½ΡΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ. ΠΠΎΠ΄Ρ Π²ΡΠ΅Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ², ΠΊΠΎΡΠΎΡΡΠ΅ Π²ΡΠ»ΠΎΠΆΠ΅Π½Ρ Π² Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ°ΡΡΠ΅, Π½Π°ΠΏΠΈΡΠ°Π½Ρ ΠΌΠ½ΠΎΠΉ. ΠΠΎΡΡΡΠΏΠ½Ρ ΠΈ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ Π·Π°ΠΏΡΡΠΊΠΎΠ² Π½Π° Π²ΡΠ΅Ρ ΡΠ΅ΡΡΠ°Ρ . ΠΠ΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΠΎΠ΅, ΡΡΠΎ Ρ Π½Π΅ ΠΌΠΎΠ³Ρ ΠΏΠΎΠΊΠ°Π·Π°ΡΡ β ΡΡΠΎ ΡΠ°ΠΌΠΈ ΡΠ΅ΡΡΡ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΎΠ½ΠΈ Π²Π΅ΡΡΡ ΠΏΠΎΡΡΠΈ 140 ΠΠ. ΠΡΠΈ ΠΌΠ°Π»Π΅ΠΉΡΠ΅ΠΌ ΠΏΠΎΠ΄ΠΎΠ·ΡΠ΅Π½ΠΈΠΈ Ρ ΠΏΡΠΎΠ²Π΅ΡΡΠ» ΠΈ ΠΊΠΎΠ΄, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΡΠ΅ΡΡΡ, ΠΈ ΡΠ°ΠΌ ΡΠ΅ΡΡ. ΠΠ°Π΄Π΅ΡΡΡ, ΡΡΠΎ ΡΡΠ°ΡΡΡ ΠΠ°ΠΌ ΠΏΠΎΠ½ΡΠ°Π²ΠΈΡΡΡ.
ΠΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΠΎΡΠ½ΠΎΠ²Π½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ ΠΈ ΠΈΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ
Π― ΠΏΠΎΡΡΠ°ΡΠ°ΡΡΡ ΠΊΡΠ°ΡΠΊΠΎ ΠΈ ΠΏΠΎΠ½ΡΡΠ½ΠΎ ΠΎΠΏΠΈΡΠ°ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΈ ΡΠΊΠ°Π·Π°ΡΡ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΡ, Ρ ΠΎΡΡ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅Π΅ Π² ΡΠ°ΠΌΠΊΠ°Ρ Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ°ΡΡΠΈ Π½Π΅ ΠΎΡΠ΅Π½Ρ Π²Π°ΠΆΠ½ΠΎ (ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΠΎ ΠΆΠ΅ ΡΠ·Π½Π°ΡΡ ΡΠ΅Π°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ). Π ΠΏΠΎΡΡΠ΅Π±Π»Π΅Π½ΠΈΠΈ ΠΏΠ°ΠΌΡΡΠΈ Π² Π΄Π°Π»ΡΠ½Π΅ΠΉΡΠ΅ΠΌ Π½ΠΈΡΠ΅Π³ΠΎ ΠΏΠΈΡΠ°ΡΡ Π½Π΅ Π±ΡΠ΄Ρ, Π·Π°ΠΌΠ΅ΡΡ ΡΠΎΠ»ΡΠΊΠΎ, ΡΡΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΠΈΠ΅ Π½Π΅ΠΏΡΠΎΡΡΡΠ΅ ΡΡΡΡΠΊΡΡΡΡ Π΄Π°Π½Π½ΡΡ (ΠΊΠ°ΠΊ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ), ΠΎΠ±ΡΡΠ½ΠΎ ΠΏΠΎΡΡΠ΅Π±Π»ΡΡΡ Π΅Π΅ Π² Π±ΠΎΠ»ΡΡΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π°Ρ , Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ·Π΄Π°ΡΡ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°ΡΠ΅Π»ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ². Π’Π°ΠΊΠΆΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΠΏΠΎΠ½ΡΡΠΈΠ΅ ΡΡΠ°Π±ΠΈΠ»ΡΠ½ΠΎΡΡΠΈ (ΡΡΡΠΎΠΉΡΠΈΠ²ΠΎΡΡΠΈ) ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΡΠΎ Π·Π½Π°ΡΠΈΡ, ΡΡΠΎ ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΡΠΉ ΠΏΠΎΡΡΠ΄ΠΎΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΏΡΠΈ ΠΈΡ ΡΠ°Π²Π΅Π½ΡΡΠ²Π΅ Π½Π΅ ΠΌΠ΅Π½ΡΠ΅ΡΡΡ. ΠΡΠΎ ΡΠΎΠΆΠ΅ Π² ΡΠ°ΠΌΠΊΠ°Ρ Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ°ΡΡΠΈ Π½Π΅Π²Π°ΠΆΠ½ΠΎ (Π² ΠΊΠΎΠ½ΡΠ΅ ΠΊΠΎΠ½ΡΠΎΠ², ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΡΡΠΎ ΠΏΡΠΈΡΠ΅ΠΏΠΈΡΡ ΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π΅Π³ΠΎ ΠΈΠ½Π΄Π΅ΠΊΡ), ΠΎΠ΄Π½Π°ΠΊΠΎ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΌΠ΅ΡΡΠ΅ ΠΏΡΠΈΠ³ΠΎΠ΄ΠΈΡΡΡ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ / Bubble sort
ΠΡΠ΄Π΅ΠΌ ΠΈΠ΄ΡΠΈ ΠΏΠΎ ΠΌΠ°ΡΡΠΈΠ²Ρ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ. ΠΡΠ»ΠΈ ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π³ΠΎ, ΠΌΠ΅Π½ΡΠ΅ΠΌ ΠΈΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ. ΠΠ΅Π»Π°Π΅ΠΌ ΡΠ°ΠΊ, ΠΏΠΎΠΊΠ° ΠΌΠ°ΡΡΠΈΠ² Π½Π΅ Π±ΡΠ΄Π΅Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½. ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΠΏΠΎΡΠ»Π΅ ΠΏΠ΅ΡΠ²ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΡΠ°ΠΌΡΠΉ Π±ΠΎΠ»ΡΡΠΎΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π±ΡΠ΄Π΅Ρ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡΡ Π² ΠΊΠΎΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Π°, Π½Π° ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠΌ ΠΌΠ΅ΡΡΠ΅. ΠΠΎΡΠ»Π΅ Π΄Π²ΡΡ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ Π½Π° ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠΌ ΠΌΠ΅ΡΡΠ΅ Π±ΡΠ΄ΡΡ ΡΡΠΎΡΡΡ Π΄Π²Π° Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°, ΠΈ ΡΠ°ΠΊ Π΄Π°Π»Π΅Π΅. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, Π½Π΅ Π±ΠΎΠ»Π΅Π΅ ΡΠ΅ΠΌ ΠΏΠΎΡΠ»Π΅ n ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ² Π±ΡΠ΄Π΅Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° Π² Ρ ΡΠ΄ΡΠ΅ΠΌ ΠΈ ΡΡΠ΅Π΄Π½Π΅ΠΌ ΡΠ»ΡΡΠ°Π΅ β O(n 2 ), Π² Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ β O(n).
Π¨Π΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Shaker sort
(ΡΠ°ΠΊΠΆΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½Π° ΠΊΠ°ΠΊ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠΈΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΈ ΠΊΠΎΠΊΡΠ΅ΠΉΠ»ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°). ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ Π½Π° ΡΠ΅ΡΡΠ°Ρ , Π² ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ°Π»Π΅Π½ΡΠΊΠΈΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΡΡΠΎΡΡ Π² ΠΊΠΎΠ½ΡΠ΅ (ΠΈΡ Π΅ΡΠ΅ Π½Π°Π·ΡΠ²Π°ΡΡ Β«ΡΠ΅ΡΠ΅ΠΏΠ°Ρ Π°ΠΌΠΈΒ»). Π’Π°ΠΊΠΎΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π±ΡΠ΄Π΅Ρ ΡΠ΄Π²ΠΈΠ³Π°ΡΡΡΡ Π²ΡΠ΅Π³ΠΎ Π½Π° ΠΎΠ΄Π½Ρ ΠΏΠΎΠ·ΠΈΡΠΈΡ Π²Π»Π΅Π²ΠΎ. ΠΠΎΡΡΠΎΠΌΡ Π±ΡΠ΄Π΅ΠΌ ΠΈΠ΄ΡΠΈ Π½Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ, Π½ΠΎ ΠΈ ΡΠΏΡΠ°Π²Π° Π½Π°Π»Π΅Π²ΠΎ. ΠΡΠ΄Π΅ΠΌ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°ΡΡ Π΄Π²Π° ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ begin ΠΈ end, ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°ΡΡΠΈΡ , ΠΊΠ°ΠΊΠΎΠΉ ΠΎΡΡΠ΅Π·ΠΎΠΊ ΠΌΠ°ΡΡΠΈΠ²Π° Π΅ΡΠ΅ Π½Π΅ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½. ΠΠ° ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΡΠΈ Π΄ΠΎΡΡΠΈΠΆΠ΅Π½ΠΈΠΈ end Π²ΡΡΠΈΡΠ°Π΅ΠΌ ΠΈΠ· Π½Π΅Π³ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡΡ ΠΈ Π΄Π²ΠΈΠΆΠ΅ΠΌΡΡ ΡΠΏΡΠ°Π²Π° Π½Π°Π»Π΅Π²ΠΎ, Π°Π½Π°Π»ΠΎΠ³ΠΈΡΠ½ΠΎ, ΠΏΡΠΈ Π΄ΠΎΡΡΠΈΠΆΠ΅Π½ΠΈΠΈ begin ΠΏΡΠΈΠ±Π°Π²Π»ΡΠ΅ΠΌ Π΅Π΄ΠΈΠ½ΠΈΡΡ ΠΈ Π΄Π²ΠΈΠ³Π°Π΅ΠΌΡΡ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ°ΠΊΠ°Ρ ΠΆΠ΅, ΠΊΠ°ΠΊ ΠΈ Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ, ΠΎΠ΄Π½Π°ΠΊΠΎ ΡΠ΅Π°Π»ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π»ΡΡΡΠ΅.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°ΡΡΠ΅ΡΠΊΠΎΠΉ / Comb sort
ΠΡΠ΅ ΠΎΠ΄Π½Π° ΠΌΠΎΠ΄ΠΈΡΠΈΠΊΠ°ΡΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ. ΠΠ»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ ΠΈΠ·Π±Π°Π²ΠΈΡΡΡΡ ΠΎΡ Β«ΡΠ΅ΡΠ΅ΠΏΠ°Ρ Β», Π±ΡΠ΄Π΅ΠΌ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π²Π»ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΡΠΎΡΡΠΈΠ΅ Π½Π° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΈ. ΠΠ°ΡΠΈΠΊΡΠΈΡΡΠ΅ΠΌ Π΅Π³ΠΎ ΠΈ Π±ΡΠ΄Π΅ΠΌ ΠΈΠ΄ΡΠΈ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ, ΡΡΠ°Π²Π½ΠΈΠ²Π°Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΡΠΎΡΡΠΈΠ΅ Π½Π° ΡΡΠΎΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΈ, ΠΏΠ΅ΡΠ΅ΡΡΠ°Π²Π»ΡΡ ΠΈΡ , Π΅ΡΠ»ΠΈ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΡΡΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ Β«ΡΠ΅ΡΠ΅ΠΏΠ°Ρ Π°ΠΌΒ» Π±ΡΡΡΡΠΎ Π΄ΠΎΠ±ΡΠ°ΡΡΡΡ Π² Π½Π°ΡΠ°Π»ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠΏΡΠΈΠΌΠ°Π»ΡΠ½ΠΎ ΠΈΠ·Π½Π°ΡΠ°Π»ΡΠ½ΠΎ Π²Π·ΡΡΡ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΡΠ°Π²Π½ΡΠΌ Π΄Π»ΠΈΠ½Π΅ ΠΌΠ°ΡΡΠΈΠ²Π°, Π° Π΄Π°Π»Π΅Π΅ Π΄Π΅Π»ΠΈΡΡ Π΅Π³ΠΎ Π½Π° Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ, ΡΠ°Π²Π½ΡΠΉ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ 1.247. ΠΠΎΠ³Π΄Π° ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠ΅ ΡΡΠ°Π½Π΅Ρ ΡΠ°Π²Π½ΠΎ Π΅Π΄ΠΈΠ½ΠΈΡΠ΅, Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ. Π Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° ΡΠ°Π²Π½Π° O(nlogn), Π² Ρ ΡΠ΄ΡΠ΅ΠΌ β O(n 2 ). ΠΠ°ΠΊΠ°Ρ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΌΠ½Π΅ Π½Π΅ ΠΎΡΠ΅Π½Ρ ΠΏΠΎΠ½ΡΡΠ½ΠΎ, Π½Π° ΠΏΡΠ°ΠΊΡΠΈΠΊΠ΅ ΠΏΠΎΡ ΠΎΠΆΠ΅ Π½Π° O(nlogn).
ΠΠ± ΡΡΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°Ρ (ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ, ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΠΈ ΡΠ°ΡΡΠ΅ΡΠΊΠΎΠΉ) ΡΠ°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΠΈΡΠ°ΡΡ Π·Π΄Π΅ΡΡ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ / Insertion sort
Π‘ΠΎΠ·Π΄Π°Π΄ΠΈΠΌ ΠΌΠ°ΡΡΠΈΠ², Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΏΠΎΡΠ»Π΅ Π·Π°Π²Π΅ΡΡΠ΅Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π±ΡΠ΄Π΅Ρ Π»Π΅ΠΆΠ°ΡΡ ΠΎΡΠ²Π΅Ρ. ΠΡΠ΄Π΅ΠΌ ΠΏΠΎΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎ Π²ΡΡΠ°Π²Π»ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΈΠ· ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅-ΠΎΡΠ²Π΅ΡΠ΅ Π²ΡΠ΅Π³Π΄Π° Π±ΡΠ»ΠΈ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Ρ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ β O(n 2 ), Π² Π»ΡΡΡΠ΅ΠΌ β O(n). Π Π΅Π°Π»ΠΈΠ·ΠΎΠ²ΡΠ²Π°ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠ΄ΠΎΠ±Π½Π΅Π΅ ΠΏΠΎ-Π΄ΡΡΠ³ΠΎΠΌΡ (ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ Π½ΠΎΠ²ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈ ΡΠ΅Π°Π»ΡΠ½ΠΎ ΡΡΠΎ-ΡΠΎ Π²ΡΡΠ°Π²Π»ΡΡΡ Π² Π½Π΅Π³ΠΎ ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠ»ΠΎΠΆΠ½ΠΎ): ΠΏΡΠΎΡΡΠΎ ΡΠ΄Π΅Π»Π°Π΅ΠΌ ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½ Π±ΡΠ» Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΡΠ΅ΡΠΈΠΊΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°, Π²ΠΌΠ΅ΡΡΠΎ Π²ΡΡΠ°Π²ΠΊΠΈ Π±ΡΠ΄Π΅ΠΌ ΠΌΠ΅Π½ΡΡΡ ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Ρ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠΈΠΌ, ΠΏΠΎΠΊΠ° ΠΎΠ½ΠΈ ΡΡΠΎΡΡ Π² Π½Π΅ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π° / Shellsort
ΠΠ΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΠ»Π΅Π·Π½ΡΡ ΡΡΡΠ»ΠΎΠΊ:
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ / Tree sort
ΠΡΠ΄Π΅ΠΌ Π²ΡΡΠ°Π²Π»ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² Π΄Π²ΠΎΠΈΡΠ½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ ΠΏΠΎΠΈΡΠΊΠ°. ΠΠΎΡΠ»Π΅ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π²ΡΡΠ°Π²Π»Π΅Π½Ρ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΠΎΠ±ΠΎΠΉΡΠΈ Π΄Π΅ΡΠ΅Π²ΠΎ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ ΠΈ ΠΏΠΎΠ»ΡΡΠΈΡΡ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ². ΠΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠ±Π°Π»Π°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ ΠΊΡΠ°ΡΠ½ΠΎ-ΡΠ΅ΡΠ½ΠΎΠ΅, Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° Π±ΡΠ΄Π΅Ρ ΡΠ°Π²Π½Π° O(nlogn) Π² Ρ ΡΠ΄ΡΠ΅ΠΌ, ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅. Π ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ ΠΊΠΎΠ½ΡΠ΅ΠΉΠ½Π΅Ρ multiset.
ΠΠ΄Π΅ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΠΈΡΠ°ΡΡ ΠΏΡΠΎ Π΄Π΅ΡΠ΅Π²ΡΡ ΠΏΠΎΠΈΡΠΊΠ°:
ΠΠ½ΠΎΠΌΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Gnome sort
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΡ ΠΎΠΆ Π½Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ. ΠΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΠΌ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π΅ΡΠ»ΠΈ ΠΎΠ½ Π±ΠΎΠ»ΡΡΠ΅ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅Π³ΠΎ ΠΈΠ»ΠΈ ΠΎΠ½ ΠΏΠ΅ΡΠ²ΡΠΉ β ΡΠΌΠ΅ΡΠ°Π΅ΠΌ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠΎΠ·ΠΈΡΠΈΡ Π²ΠΏΡΠ°Π²ΠΎ, ΠΈΠ½Π°ΡΠ΅ ΠΌΠ΅Π½ΡΠ΅ΠΌ ΡΠ΅ΠΊΡΡΠΈΠΉ ΠΈ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΠΈ ΡΠΌΠ΅ΡΠ°Π΅ΠΌΡΡ Π²Π»Π΅Π²ΠΎ.
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ / Selection sort
ΠΠ° ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ Π±ΡΠ΄Π΅ΠΌ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ ΠΏΠΎΡΠ»Π΅ ΡΠ΅ΠΊΡΡΠ΅Π³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° ΠΈ ΠΌΠ΅Π½ΡΡΡ Π΅Π³ΠΎ Ρ Π½ΠΈΠΌ, Π΅ΡΠ»ΠΈ Π½Π°Π΄ΠΎ. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΠΎΡΠ»Π΅ i-ΠΎΠΉ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΈ ΠΏΠ΅ΡΠ²ΡΠ΅ i ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π±ΡΠ΄ΡΡ ΡΡΠΎΡΡΡ Π½Π° ΡΠ²ΠΎΠΈΡ ΠΌΠ΅ΡΡΠ°Ρ . ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°: O(n 2 ) Π² Π»ΡΡΡΠ΅ΠΌ, ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅. ΠΡΠΆΠ½ΠΎ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ Π΄Π²ΡΠΌΡ ΡΠΏΠΎΡΠΎΠ±Π°ΠΌΠΈ β ΡΠΎΡ ΡΠ°Π½ΡΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ ΠΈ Π΅Π³ΠΎ ΠΈΠ½Π΄Π΅ΠΊΡ ΠΈΠ»ΠΈ ΠΏΡΠΎΡΡΠΎ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π²Π»ΡΡ ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Ρ ΡΠ°ΡΡΠΌΠ°ΡΡΠΈΠ²Π°Π΅ΠΌΡΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ½ΠΈ ΡΡΠΎΡΡ Π² Π½Π΅ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅. ΠΠ΅ΡΠ²ΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΠΎΠΊΠ°Π·Π°Π»ΡΡ Π½Π΅ΠΌΠ½ΠΎΠ³ΠΎ Π±ΡΡΡΡΠ΅Π΅, ΠΏΠΎΡΡΠΎΠΌΡ ΠΎΠ½ ΠΈ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½.
ΠΠΈΡΠ°ΠΌΠΈΠ΄Π°Π»ΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Heapsort
Π Π°Π·Π²ΠΈΡΠΈΠ΅ ΠΈΠ΄Π΅ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΠ±ΠΎΡΠΎΠΌ. ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ ΡΡΡΡΠΊΡΡΡΠΎΠΉ Π΄Π°Π½Π½ΡΡ Β«ΠΊΡΡΠ°Β» (ΠΈΠ»ΠΈ Β«ΠΏΠΈΡΠ°ΠΌΠΈΠ΄Π°Β», ΠΎΡΠΊΡΠ΄Π° ΠΈ Π½Π°Π·Π²Π°Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°). ΠΠ½Π° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΠ΅Ρ ΠΏΠΎΠ»ΡΡΠ°ΡΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π·Π° O(1), Π΄ΠΎΠ±Π°Π²Π»ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΈ ΠΈΠ·Π²Π»Π΅ΠΊΠ°Ρ ΠΌΠΈΠ½ΠΈΠΌΡΠΌ Π·Π° O(logn). Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° O(nlogn) Π² Ρ ΡΠ΄ΡΠ΅ΠΌ, ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅. Π Π΅Π°Π»ΠΈΠ·ΠΎΠ²ΡΠ²Π°Π» ΠΊΡΡΡ Ρ ΡΠ°ΠΌ, Ρ ΠΎΡΡ Π² Π‘++ ΠΈ Π΅ΡΡΡ ΠΊΠΎΠ½ΡΠ΅ΠΉΠ½Π΅Ρ priority_queue, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΡΡΠΎΡ ΠΊΠΎΠ½ΡΠ΅ΠΉΠ½Π΅Ρ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΡΠΉ.
ΠΠΎΡΠΈΡΠ°ΡΡ ΠΏΡΠΎ ΠΊΡΡΡ ΠΌΠΎΠΆΠ½ΠΎ Π·Π΄Π΅ΡΡ:
ΠΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Quicksort
ΠΡΠ±Π΅ΡΠ΅ΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ. ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ ΠΏΠ΅ΡΠ΅ΠΊΠΈΠ½Π΅ΠΌ Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΠΌΠ΅Π½ΡΡΠΈΠ΅ Π΅Π³ΠΎ, Π½Π°Π»Π΅Π²ΠΎ, Π° Π±ΠΎΠ»ΡΡΠΈΠ΅ β Π½Π°ΠΏΡΠ°Π²ΠΎ. Π Π΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ Π²ΡΠ·ΠΎΠ²Π΅ΠΌΡΡ ΠΎΡ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· ΡΠ°ΡΡΠ΅ΠΉ. Π ΠΈΡΠΎΠ³Π΅ ΠΏΠΎΠ»ΡΡΠΈΠΌ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ², ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ΅Π½ΡΡΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΡΡΠΎΡΠ» ΡΠ°Π½ΡΡΠ΅ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π±ΠΎΠ»ΡΡΠ΅Π³ΠΎ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°: O(nlogn) Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅, O(n 2 ). ΠΠ°ΠΈΡ ΡΠ΄ΡΠ°Ρ ΠΎΡΠ΅Π½ΠΊΠ° Π΄ΠΎΡΡΠΈΠ³Π°Π΅ΡΡΡ ΠΏΡΠΈ Π½Π΅ΡΠ΄Π°ΡΠ½ΠΎΠΌ Π²ΡΠ±ΠΎΡΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. ΠΠΎΡ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΡΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠΎΠ²Π΅ΡΡΠ΅Π½Π½ΠΎ ΡΡΠ°Π½Π΄Π°ΡΡΠ½Π°, ΠΈΠ΄Π΅ΠΌ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΡΠ»Π΅Π²Π° ΠΈ ΡΠΏΡΠ°Π²Π°, Π½Π°Ρ ΠΎΠ΄ΠΈΠΌ ΠΏΠ°ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΡΠ°ΠΊΠΈΡ , ΡΡΠΎ Π»Π΅Π²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π±ΠΎΠ»ΡΡΠ΅ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ, Π° ΠΏΡΠ°Π²ΡΠΉ ΠΌΠ΅Π½ΡΡΠ΅, ΠΈ ΠΌΠ΅Π½ΡΠ΅ΠΌ ΠΈΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ. ΠΠΎΠΌΠΈΠΌΠΎ ΡΠΈΡΡΠΎΠΉ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΡΡΠ°ΡΡΠ²ΠΎΠ²Π°Π»Π° Π² ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΈ ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ΡΡΠ°Ρ ΠΏΡΠΈ ΠΌΠ°Π»ΠΎΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π½Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ. ΠΠΎΠ½ΡΡΠ°Π½ΡΠ° ΠΏΠΎΠ΄ΠΎΠ±ΡΠ°Π½Π° ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ, Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ β Π½Π°ΠΈΠ»ΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ°Ρ Π΄Π»Ρ ΡΡΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ (Ρ ΠΎΡΡ Π½Π΅ ΡΡΠΎΠΈΡ ΠΈΠ·-Π·Π° ΡΡΠΎΠ³ΠΎ Π΄ΡΠΌΠ°ΡΡ, ΡΡΠΎ ΠΎΠ½Π° ΡΠ°ΠΌΠ°Ρ Π±ΡΡΡΡΠ°Ρ ΠΈΠ· ΠΊΠ²Π°Π΄ΡΠ°ΡΠΈΡΠ½ΡΡ ).
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ / Merge sort
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΠΎΡΠ½ΠΎΠ²Π°Π½Π½Π°Ρ Π½Π° ΠΏΠ°ΡΠ°Π΄ΠΈΠ³ΠΌΠ΅ Β«ΡΠ°Π·Π΄Π΅Π»ΡΠΉ ΠΈ Π²Π»Π°ΡΡΠ²ΡΠΉΒ». Π Π°Π·Π΄Π΅Π»ΠΈΠΌ ΠΌΠ°ΡΡΠΈΠ² ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ, ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΡΠ΅ΠΌ ΡΠ°ΡΡΠΈ, ΠΏΠΎΡΠ»Π΅ ΡΠ΅Π³ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΠΌ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ ΡΠ»ΠΈΡΠ½ΠΈΡ: ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΠΌ Π΄Π²Π° ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ, ΠΎΠ΄ΠΈΠ½ Π½Π° ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠ΅ΡΠ²ΠΎΠΉ ΡΠ°ΡΡΠΈ, Π²ΡΠΎΡΠΎΠΉ β Π½Π° ΡΠ΅ΠΊΡΡΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²ΡΠΎΡΠΎΠΉ ΡΠ°ΡΡΠΈ. ΠΠ· ΡΡΠΈΡ Π΄Π²ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π²ΡΠ±ΠΈΡΠ°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ, Π²ΡΡΠ°Π²Π»ΡΠ΅ΠΌ Π² ΠΎΡΠ²Π΅Ρ ΠΈ ΡΠ΄Π²ΠΈΠ³Π°Π΅ΠΌ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ. Π‘Π»ΠΈΡΠ½ΠΈΠ΅ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π·Π° O(n), ΡΡΠΎΠ²Π½Π΅ΠΉ Π²ΡΠ΅Π³ΠΎ logn, ΠΏΠΎΡΡΠΎΠΌΡ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° O(nlogn). ΠΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ Π·Π°ΡΠ°Π½Π΅Π΅ ΡΠΎΠ·Π΄Π°ΡΡ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡ Π΅Π³ΠΎ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠ° ΡΡΠ½ΠΊΡΠΈΠΈ. ΠΡΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½Π°, ΠΊΠ°ΠΊ ΠΈ Π±ΡΡΡΡΠ°Ρ, Π° ΠΏΠΎΡΠΎΠΌΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ΅Π½ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ Π½Π° ΠΊΠ²Π°Π΄ΡΠ°ΡΠΈΡΠ½ΡΡ ΠΏΡΠΈ Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠΌ ΡΠΈΡΠ»Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠΎΠ΄ΡΡΠ΅ΡΠΎΠΌ / Counting sort
Π‘ΠΎΠ·Π΄Π°Π΄ΠΈΠΌ ΠΌΠ°ΡΡΠΈΠ² ΡΠ°Π·ΠΌΠ΅ΡΠ° r β l, Π³Π΄Π΅ l β ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ, Π° r β ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠΎΡΠ»Π΅ ΡΡΠΎΠ³ΠΎ ΠΏΡΠΎΠΉΠ΄Π΅ΠΌ ΠΏΠΎ ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΈ ΠΏΠΎΠ΄ΡΡΠΈΡΠ°Π΅ΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠΉ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. Π’Π΅ΠΏΠ΅ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΠΉΡΠΈ ΠΏΠΎ ΠΌΠ°ΡΡΠΈΠ²Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ ΠΈ Π²ΡΠΏΠΈΡΠ°ΡΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΡΡΠΎΠ»ΡΠΊΠΎ ΡΠ°Π·, ΡΠΊΠΎΠ»ΡΠΊΠΎ Π½ΡΠΆΠ½ΠΎ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° β O(n + r β l). ΠΠΎΠΆΠ½ΠΎ ΠΌΠΎΠ΄ΠΈΡΠΈΡΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΡΡΠΎΠ±Ρ ΠΎΠ½ ΡΡΠ°Π» ΡΡΠ°Π±ΠΈΠ»ΡΠ½ΡΠΌ: Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΠΌ ΠΌΠ΅ΡΡΠΎ, Π³Π΄Π΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΡΡΠΎΡΡΡ ΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ (ΡΡΠΎ ΠΏΡΠΎΡΡΠΎ ΠΏΡΠ΅ΡΠΈΠΊΡΠ½ΡΠ΅ ΡΡΠΌΠΌΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠΉ) ΠΈ Π±ΡΠ΄Π΅ΠΌ ΠΈΠ΄ΡΠΈ ΠΏΠΎ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΌΠ°ΡΡΠΈΠ²Ρ ΡΠ»Π΅Π²Π° Π½Π°ΠΏΡΠ°Π²ΠΎ, ΡΡΠ°Π²Ρ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π½Π° ΠΏΡΠ°Π²ΠΈΠ»ΡΠ½ΠΎΠ΅ ΠΌΠ΅ΡΡΠΎ ΠΈ ΡΠ²Π΅Π»ΠΈΡΠΈΠ²Π°Ρ ΠΏΠΎΠ·ΠΈΡΠΈΡ Π½Π° 1. ΠΡΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π½Π΅ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π»Π°ΡΡ, ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π±ΠΎΠ»ΡΡΠΈΠ½ΡΡΠ²ΠΎ ΡΠ΅ΡΡΠΎΠ² ΡΠΎΠ΄Π΅ΡΠΆΠ°Π»ΠΎ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ Π±ΠΎΠ»ΡΡΠΈΠ΅ ΡΠΈΡΠ»Π°, Π½Π΅ ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠΈΠ΅ ΡΠΎΠ·Π΄Π°ΡΡ ΠΌΠ°ΡΡΠΈΠ² ΡΡΠ΅Π±ΡΠ΅ΠΌΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ°. ΠΠ΄Π½Π°ΠΊΠΎ ΠΎΠ½Π°, ΡΠ΅ΠΌ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅, ΠΏΡΠΈΠ³ΠΎΠ΄ΠΈΠ»Π°ΡΡ.
ΠΠ»ΠΎΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Bucket sort
(ΡΠ°ΠΊΠΆΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½Π° ΠΊΠ°ΠΊ ΠΊΠΎΡΠ·ΠΈΠ½Π½Π°Ρ ΠΈ ΠΊΠ°ΡΠΌΠ°Π½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°). ΠΡΡΡΡ l β ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ, Π° r β ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π°. Π Π°Π·ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π½Π° Π±Π»ΠΎΠΊΠΈ, Π² ΠΏΠ΅ΡΠ²ΠΎΠΌ Π±ΡΠ΄ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΎΡ l Π΄ΠΎ l + k, Π²ΠΎ Π²ΡΠΎΡΠΎΠΌ β ΠΎΡ l + k Π΄ΠΎ l + 2k ΠΈ Ρ.Π΄., Π³Π΄Π΅ k = (r β l) / ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π±Π»ΠΎΠΊΠΎΠ². Π ΠΎΠ±ΡΠ΅ΠΌ-ΡΠΎ, Π΅ΡΠ»ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π±Π»ΠΎΠΊΠΎΠ² ΡΠ°Π²Π½ΠΎ Π΄Π²ΡΠΌ, ΡΠΎ Π΄Π°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΡΠ΅Π²ΡΠ°ΡΠ°Π΅ΡΡΡ Π² ΡΠ°Π·Π½ΠΎΠ²ΠΈΠ΄Π½ΠΎΡΡΡ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° ΡΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π΅ΡΡΠ½Π°, Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π·Π°Π²ΠΈΡΠΈΡ ΠΈ ΠΎΡ Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ , ΠΈ ΠΎΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° Π±Π»ΠΎΠΊΠΎΠ². Π£ΡΠ²Π΅ΡΠΆΠ΄Π°Π΅ΡΡΡ, ΡΡΠΎ Π½Π° ΡΠ΄Π°ΡΠ½ΡΡ Π΄Π°Π½Π½ΡΡ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ. Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΡΡΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΎΠΊΠ°Π·Π°Π»Π°ΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· ΡΠ°ΠΌΡΡ ΡΡΡΠ΄Π½ΡΡ Π·Π°Π΄Π°Ρ. ΠΠΎΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΠΎ ΡΠ°ΠΊ: ΠΏΡΠΎΡΡΠΎ ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ Π½ΠΎΠ²ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ, ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΈ ΡΠΊΠ»Π΅ΠΈΠ²Π°ΡΡ. ΠΠ΄Π½Π°ΠΊΠΎ ΡΠ°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ Π²ΡΠ΅ ΠΆΠ΅ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΡΠΉ ΠΈ ΠΌΠ΅Π½Ρ Π½Π΅ ΡΡΡΡΠΎΠΈΠ». Π ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎΠΉ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΈΠ΄Π΅ΠΉ:
1) ΠΠ΅ Π±ΡΠ΄Π΅ΠΌ ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ Π½ΠΎΠ²ΡΡ ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ². ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ ΡΠ΅Ρ Π½ΠΈΠΊΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΠΎΠ΄ΡΡΠ΅ΡΠΎΠΌ β ΠΏΠΎΠ΄ΡΡΠΈΡΠ°Π΅ΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΌ Π±Π»ΠΎΠΊΠ΅, ΠΏΡΠ΅ΡΠΈΠΊΡΠ½ΡΠ΅ ΡΡΠΌΠΌΡ ΠΈ, ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΠΎΠ·ΠΈΡΠΈΡ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π² ΠΌΠ°ΡΡΠΈΠ²Π΅.
2) ΠΠ΅ Π±ΡΠ΄Π΅ΠΌ Π·Π°ΠΏΡΡΠΊΠ°ΡΡΡΡ ΠΈΠ· ΠΏΡΡΡΡΡ Π±Π»ΠΎΠΊΠΎΠ². ΠΠ°Π½Π΅ΡΠ΅ΠΌ ΠΈΠ½Π΄Π΅ΠΊΡΡ Π½Π΅ΠΏΡΡΡΡΡ Π±Π»ΠΎΠΊΠΎΠ² Π² ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈ Π·Π°ΠΏΡΡΡΠΈΠΌΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΡ Π½ΠΈΡ .
3) ΠΡΠΎΠ²Π΅ΡΠΈΠΌ, ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½ Π»ΠΈ ΠΌΠ°ΡΡΠΈΠ². ΠΡΠΎ Π½Π΅ ΡΡ ΡΠ΄ΡΠΈΡ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π²ΡΠ΅ ΡΠ°Π²Π½ΠΎ Π½ΡΠΆΠ½ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΠΏΡΠΎΡ ΠΎΠ΄ Ρ ΡΠ΅Π»ΡΡ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΠ° ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌΠ°, ΠΎΠ΄Π½Π°ΠΊΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΡΠΊΠΎΡΠΈΡΡΡΡ Π½Π° ΡΠ°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π΄Π°Π½Π½ΡΡ , Π²Π΅Π΄Ρ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π²ΡΡΠ°Π²Π»ΡΡΡΡΡ Π² Π½ΠΎΠ²ΡΠ΅ Π±Π»ΠΎΠΊΠΈ Π² ΡΠΎΠΌ ΠΆΠ΅ ΠΏΠΎΡΡΠ΄ΠΊΠ΅, ΡΡΠΎ ΠΈ Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠΌ ΠΌΠ°ΡΡΠΈΠ²Π΅.
4) ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ»ΡΡΠΈΠ»ΡΡ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ Π³ΡΠΎΠΌΠΎΠ·Π΄ΠΊΠΈΠΌ, ΠΏΡΠΈ Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΎΠ½ ΠΊΡΠ°ΠΉΠ½Π΅ Π½Π΅ΡΡΡΠ΅ΠΊΡΠΈΠ²Π΅Π½. ΠΠΎ ΡΠ°ΠΊΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ, ΡΡΠΎ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ Π½Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ ΡΡΠΊΠΎΡΡΠ΅Ρ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ Π² 10 ΡΠ°Π·.
ΠΠΎΡΠ°Π·ΡΡΠ΄Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Radix sort
(ΡΠ°ΠΊΠΆΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½Π° ΠΊΠ°ΠΊ ΡΠΈΡΡΠΎΠ²Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°). Π‘ΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π΄Π²Π΅ Π²Π΅ΡΡΠΈΠΈ ΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, Π² ΠΊΠΎΡΠΎΡΡΡ , Π½Π° ΠΌΠΎΠΉ Π²Π·Π³Π»ΡΠ΄, ΠΌΠ°Π»ΠΎ ΠΎΠ±ΡΠ΅Π³ΠΎ, ΠΊΡΠΎΠΌΠ΅ ΠΈΠ΄Π΅ΠΈ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ ΡΠΈΡΠ»Π° Π² ΠΊΠ°ΠΊΠΎΠΉ-Π»ΠΈΠ±ΠΎ ΡΠΈΡΡΠ΅ΠΌΠ΅ ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΉ).
LSD (least significant digit):
ΠΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠΌ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ Π² Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΌ Π²ΠΈΠ΄Π΅. ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π±ΡΠ΄Π΅ΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠΈΡΠ»Π° ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΡΠΎΠ±Ρ ΠΎΠ½ΠΈ Π±ΡΠ»ΠΈ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Ρ ΠΏΠΎ ΠΏΠ΅ΡΠ²ΡΠΌ k * i Π±ΠΈΡΠ°ΠΌ, Π³Π΄Π΅ k β Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΠ°. ΠΠ· Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΡΡΠ°Π±ΠΈΠ»ΡΠ½ΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΏΠΎ Π½ΠΎΠ²ΡΠΌ k Π±ΠΈΡΠ°ΠΌ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΠΈΠ΄Π΅Π°Π»ΡΠ½ΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΠΈΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΠΎΠ΄ΡΡΠ΅ΡΠΎΠΌ (Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ 2 k ΠΏΠ°ΠΌΡΡΠΈ ΠΈ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ, ΡΡΠΎ Π½Π΅ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΡΠΈ ΡΠ΄Π°ΡΠ½ΠΎΠΌ Π²ΡΠ±ΠΎΡΠ΅ ΠΊΠΎΠ½ΡΡΠ°Π½ΡΡ). ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°: O(n), Π΅ΡΠ»ΠΈ ΡΡΠΈΡΠ°ΡΡ, ΡΡΠΎ ΡΠΈΡΠ»Π° ΡΠΈΠΊΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ° (Π° Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π΅Π»ΡΠ·Ρ Π±ΡΠ»ΠΎ Π±Ρ ΡΡΠΈΡΠ°ΡΡ, ΡΡΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ Π΄Π²ΡΡ ΡΠΈΡΠ΅Π» Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π·Π° Π΅Π΄ΠΈΠ½ΠΈΡΡ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ). Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΠΏΡΠΎΡΡΠ°.
MSD (most significant digit):
ΠΠ° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅, Π½Π΅ΠΊΠΎΡΠΎΡΠ°Ρ ΡΠ°Π·Π½ΠΎΠ²ΠΈΠ΄Π½ΠΎΡΡΡ Π±Π»ΠΎΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. Π ΠΎΠ΄ΠΈΠ½ Π±Π»ΠΎΠΊ Π±ΡΠ΄ΡΡ ΠΏΠΎΠΏΠ°Π΄Π°ΡΡ ΡΠΈΡΠ»Π° Ρ ΡΠ°Π²Π½ΡΠΌΠΈ k Π±ΠΈΡΠ°ΠΌΠΈ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° ΡΠ°ΠΊΠ°Ρ ΠΆΠ΅, ΠΊΠ°ΠΊ ΠΈ Ρ LSD Π²Π΅ΡΡΠΈΠΈ. Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ ΠΎΡΠ΅Π½Ρ ΠΏΠΎΡ ΠΎΠΆΠ° Π½Π° Π±Π»ΠΎΡΠ½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ, Π½ΠΎ ΠΏΡΠΎΡΠ΅. Π Π½Π΅ΠΉ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΡΡΠ½ΠΊΡΠΈΡ digit, ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½Π°Ρ Π² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ LSD Π²Π΅ΡΡΠΈΠΈ.
ΠΠΈΡΠΎΠ½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° / Bitonic sort:
ΠΠ΄Π΅Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΠΈΡΡ ΠΎΠ΄Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΡΠ΅ΡΡΡ Π² Π±ΠΈΡΠΎΠ½Π½ΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ β ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΡΠ½Π°ΡΠ°Π»Π° Π²ΠΎΠ·ΡΠ°ΡΡΠ°Π΅Ρ, Π° ΠΏΠΎΡΠΎΠΌ ΡΠ±ΡΠ²Π°Π΅Ρ. ΠΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ: ΡΠ°Π·ΠΎΠ±ΡΠ΅ΠΌ ΠΌΠ°ΡΡΠΈΠ² Π½Π° Π΄Π²Π΅ ΡΠ°ΡΡΠΈ, ΡΠΎΠ·Π΄Π°Π΄ΠΈΠΌ Π΄Π²Π° ΠΌΠ°ΡΡΠΈΠ²Π°, Π² ΠΏΠ΅ΡΠ²ΡΠΉ Π΄ΠΎΠ±Π°Π²ΠΈΠΌ Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ, ΡΠ°Π²Π½ΡΠ΅ ΠΌΠΈΠ½ΠΈΠΌΡΠΌΡ ΠΈΠ· ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· Π΄Π²ΡΡ ΡΠ°ΡΡΠ΅ΠΉ, Π° Π²ΠΎ Π²ΡΠΎΡΠΎΠΉ β ΡΠ°Π²Π½ΡΠ΅ ΠΌΠ°ΠΊΡΠΈΠΌΡΠΌΡ. Π£ΡΠ²Π΅ΡΠΆΠ΄Π°Π΅ΡΡΡ, ΡΡΠΎ ΠΏΠΎΠ»ΡΡΠ°ΡΡΡ Π΄Π²Π΅ Π±ΠΈΡΠΎΠ½Π½ΡΠ΅ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ, ΠΊΠ°ΠΆΠ΄ΡΡ ΠΈΠ· ΠΊΠΎΡΠΎΡΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΡΠ΅ΠΌ ΠΆΠ΅ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΏΠΎΡΠ»Π΅ ΡΠ΅Π³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ ΡΠΊΠ»Π΅ΠΈΡΡ Π΄Π²Π° ΠΌΠ°ΡΡΠΈΠ²Π° (ΡΠ°ΠΊ ΠΊΠ°ΠΊ Π»ΡΠ±ΠΎΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π΅Π½ Π»ΡΠ±ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π²ΡΠΎΡΠΎΠ³ΠΎ). ΠΠ»Ρ ΡΠΎΠ³ΠΎ, ΡΡΠΎΠ±Ρ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΡ ΠΈΡΡ ΠΎΠ΄Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² Π² Π±ΠΈΡΠΎΠ½Π½ΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ, ΡΠ΄Π΅Π»Π°Π΅ΠΌ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅: Π΅ΡΠ»ΠΈ ΠΌΠ°ΡΡΠΈΠ² ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ², ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΎΡΡΠΎ Π·Π°Π²Π΅ΡΡΠΈΡΡΡΡ, ΠΈΠ½Π°ΡΠ΅ ΡΠ°Π·Π΄Π΅Π»ΠΈΠΌ ΠΌΠ°ΡΡΠΈΠ² ΠΏΠΎΠΏΠΎΠ»Π°ΠΌ, ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΠΎ Π²ΡΠ·ΠΎΠ²Π΅ΠΌ ΠΎΡ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½ΠΎΠΊ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΠΏΠΎΡΠ»Π΅ ΡΠ΅Π³ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΡΠ΅ΠΌ ΠΏΠ΅ΡΠ²ΡΡ ΡΠ°ΡΡΡ ΠΏΠΎ ΠΏΠΎΡΡΠ΄ΠΊΡ, Π²ΡΠΎΡΡΡ Π² ΠΎΠ±ΡΠ°ΡΠ½ΠΎΠΌ ΠΏΠΎΡΡΠ΄ΠΊΠ΅ ΠΈ ΡΠΊΠ»Π΅ΠΈΠΌ. ΠΡΠ΅Π²ΠΈΠ΄Π½ΠΎ, ΠΏΠΎΠ»ΡΡΠΈΡΡΡ Π±ΠΈΡΠΎΠ½Π½Π°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ. ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°: O(nlog 2 n), ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΏΡΠΈ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΠΈ Π±ΠΈΡΠΎΠ½Π½ΠΎΠΉ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΠΌΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π»ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ, ΡΠ°Π±ΠΎΡΠ°ΡΡΡΡ Π·Π° O(nlogn), Π° Π²ΡΠ΅Π³ΠΎ ΡΡΠΎΠ²Π½Π΅ΠΉ Π±ΡΠ»ΠΎ logn. Π’Π°ΠΊΠΆΠ΅ Π·Π°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΡΠ°Π·ΠΌΠ΅Ρ ΠΌΠ°ΡΡΠΈΠ²Π° Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ ΡΠ°Π²Π΅Π½ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ Π΄Π²ΠΎΠΉΠΊΠΈ, ΡΠ°ΠΊ ΡΡΠΎ, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΠΏΡΠΈΠ΄Π΅ΡΡΡ Π΅Π³ΠΎ Π΄ΠΎΠΏΠΎΠ»Π½ΡΡΡ ΡΠΈΠΊΡΠΈΠ²Π½ΡΠΌΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ (ΡΡΠΎ Π½Π΅ Π²Π»ΠΈΡΠ΅Ρ Π½Π° Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΡ).
Timsort
ΠΠΈΠ±ΡΠΈΠ΄Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΡΠΎΠ²ΠΌΠ΅ΡΠ°ΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ ΠΈ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ. Π Π°Π·ΠΎΠ±ΡΠ΅ΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π° Π½Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ² Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ°, ΠΏΡΠΈ ΡΡΠΎΠΌ Π±ΡΠ΄Π΅ΠΌ ΡΠ°ΡΡΠΈΡΡΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ², ΠΏΠΎΠΊΠ° ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ Π² Π½Π΅ΠΌ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Ρ. ΠΡΡΠΎΡΡΠΈΡΡΠ΅ΠΌ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΎΠΉ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, ΠΏΠΎΠ»ΡΠ·ΡΡΡΡ ΡΠ΅ΠΌ, ΡΡΠΎ ΠΎΠ½Π° ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π° ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°Ρ . ΠΠ°Π»Π΅Π΅ Π±ΡΠ΄Π΅ΠΌ ΡΠ»ΠΈΠ²Π°ΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Ρ ΠΊΠ°ΠΊ Π² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ, Π±Π΅ΡΡ ΠΈΡ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ ΡΠ°Π²Π½ΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ° (ΠΈΠ½Π°ΡΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΈΠ±Π»ΠΈΠ·ΠΈΡΡΡ ΠΊ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΈΡΠ½ΠΎΠΌΡ). ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ΄ΠΎΠ±Π½ΠΎΠ³ΠΎ Ρ ΡΠ°Π½ΠΈΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Ρ Π² ΡΡΠ΅ΠΊΠ΅, ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Ρ ΠΈΠ½Π²Π°ΡΠΈΠ°Π½Ρ β ΡΠ΅ΠΌ Π΄Π°Π»ΡΡΠ΅ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠ΅ΠΌ Π±ΠΎΠ»ΡΡΠ΅ ΡΠ°Π·ΠΌΠ΅Ρ, ΠΈ ΡΠ»ΠΈΠ²Π°ΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Ρ Π½Π° Π²Π΅ΡΡ ΡΡΠΊΠ΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΡΠ°Π·ΠΌΠ΅Ρ ΡΡΠ΅ΡΡΠ΅Π³ΠΎ ΠΏΠΎ ΠΎΡΠ΄Π°Π»Π΅Π½Π½ΠΎΡΡΠΈ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²Π° Π±ΠΎΠ»ΡΡΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π΅Π½ ΡΡΠΌΠΌΠ΅ ΠΈΡ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠ². ΠΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ°: O(n) Π² Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΈ O(nlogn) Π² ΡΡΠ΅Π΄Π½Π΅ΠΌ ΠΈ Ρ ΡΠ΄ΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅. Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π½Π΅ΡΡΠΈΠ²ΠΈΠ°Π»ΡΠ½Π°, ΡΠ²Π΅ΡΠ΄ΠΎΠΉ ΡΠ²Π΅ΡΠ΅Π½Π½ΠΎΡΡΠΈ Π² Π½Π΅ΠΉ Ρ ΠΌΠ΅Π½Ρ Π½Π΅Ρ, ΠΎΠ΄Π½Π°ΠΊΠΎ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ ΠΎΠ½Π° ΠΏΠΎΠΊΠ°Π·Π°Π»Π° Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ Π½Π΅ΠΏΠ»ΠΎΡ ΠΎΠ΅ ΠΈ ΡΠΎΠ³Π»Π°ΡΡΡΡΠ΅Π΅ΡΡ Ρ ΠΌΠΎΠΈΠΌΠΈ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡΠΌΠΈ ΠΎ ΡΠΎΠΌ, ΠΊΠ°ΠΊ Π΄ΠΎΠ»ΠΆΠ½Π° ΡΠ°Π±ΠΎΡΠ°ΡΡ ΡΡΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°.
ΠΠΎΠ΄ΡΠΎΠ±Π½Π΅Π΅ timsort ΠΎΠΏΠΈΡΠ°Π½ Π·Π΄Π΅ΡΡ:
Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅
ΠΠ΅Π»Π΅Π·ΠΎ ΠΈ ΡΠΈΡΡΠ΅ΠΌΠ°
ΠΡΠΎΡΠ΅ΡΡΠΎΡ: Intel Core i7-3770 CPU 3.40 GHz
ΠΠΠ£: 8 ΠΠ
Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΠ»ΠΎΡΡ Π½Π° ΠΏΠΎΡΡΠΈ ΡΠΈΡΡΠΎΠΉ ΡΠΈΡΡΠ΅ΠΌΠ΅ Windows 10 x64, ΡΡΡΠ°Π½ΠΎΠ²Π»Π΅Π½Π½ΠΎΠΉ Π·Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π΄Π½Π΅ΠΉ Π΄ΠΎ Π·Π°ΠΏΡΡΠΊΠ°. ΠΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½Π°Ρ IDE β Microsoft Visual Studio 2015.
Π’Π΅ΡΡΡ
Π Π°Π·ΠΌΠ΅Ρ Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ
ΠΠ°ΠΊ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΠ»ΠΎΡΡ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅
ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ΅ΡΡΠ΅ Π±ΡΠ»ΠΎ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΠ»ΠΎΡΡ 20 Π·Π°ΠΏΡΡΠΊΠΎΠ², ΠΈΡΠΎΠ³ΠΎΠ²ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ β ΡΡΠ΅Π΄Π½Π΅Π΅ ΠΏΠΎ ΠΏΠΎΠ»ΡΡΠΈΠ²ΡΠΈΠΌΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΡΠΌ. ΠΠΎΡΡΠΈ Π²ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ Π±ΡΠ»ΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Ρ ΠΏΠΎΡΠ»Π΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π·Π°ΠΏΡΡΠΊΠ° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ, ΠΎΠ΄Π½Π°ΠΊΠΎ ΠΈΠ·-Π·Π° Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ ΠΎΡΠΈΠ±ΠΎΠΊ Π² ΠΊΠΎΠ΄Π΅ ΠΈ ΡΠΈΡΡΠ΅ΠΌΠ½ΡΡ Π³Π»ΡΠΊΠΎΠ² (Π²ΡΠ΅ ΠΆΠ΅ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π»ΠΎΡΡ ΠΏΠΎΡΡΠΈ Π½Π΅Π΄Π΅Π»Ρ ΡΠΈΡΡΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ) Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΈ ΡΠ΅ΡΡΡ ΠΏΡΠΈΡΠ»ΠΎΡΡ Π²ΠΏΠΎΡΠ»Π΅Π΄ΡΡΠ²ΠΈΠΈ ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°ΡΡ.
Π’ΠΎΠ½ΠΊΠΎΡΡΠΈ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ
ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΠΊΠΎΠ³ΠΎ-ΡΠΎ ΡΠ΄ΠΈΠ²ΠΈΡ, ΡΡΠΎ Π² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΡΠ°ΠΌΠΎΠ³ΠΎ ΠΏΡΠΎΡΠ΅ΡΡΠ° ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Ρ Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π» ΡΠΊΠ°Π·Π°ΡΠ΅Π»ΠΈ Π½Π° ΡΡΠ½ΠΊΡΠΈΠΈ, ΡΡΠΎ ΡΠΈΠ»ΡΠ½ΠΎ ΡΠΎΠΊΡΠ°ΡΠΈΠ»ΠΎ Π±Ρ ΠΊΠΎΠ΄. ΠΠΊΠ°Π·Π°Π»ΠΎΡΡ, ΡΡΠΎ ΡΡΠΎ Π·Π°ΠΌΠ΅ΡΠ½ΠΎ Π·Π°ΠΌΠ΅Π΄Π»ΡΠ΅Ρ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° (ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ Π½Π° 5-10%). ΠΠΎΡΡΠΎΠΌΡ Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π» ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΠΉ Π²ΡΠ·ΠΎΠ² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ (ΡΡΠΎ, ΠΊΠΎΠ½Π΅ΡΠ½ΠΎ, Π½Π΅ ΠΎΡΡΠ°Π·ΠΈΠ»ΠΎΡΡ Π±Ρ Π½Π° ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠΊΠΎΡΠΎΡΡΠΈ, Π½ΠΎβ¦ Π²ΡΠ΅ ΠΆΠ΅ Ρ ΠΎΡΠ΅ΡΡΡ ΡΠ»ΡΡΡΠΈΡΡ ΠΈ Π°Π±ΡΠΎΠ»ΡΡΠ½ΡΡ). ΠΠΎ ΡΠΎΠΉ ΠΆΠ΅ ΠΏΡΠΈΡΠΈΠ½Π΅ Π±ΡΠ»ΠΈ Π·Π°ΠΌΠ΅Π½Π΅Π½Ρ Π²Π΅ΠΊΡΠΎΡΡ Π½Π° ΠΎΠ±ΡΡΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ, Π½Π΅ Π±ΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Ρ ΡΠ°Π±Π»ΠΎΠ½Ρ ΠΈ ΡΡΠ½ΠΊΡΠΈΠΈ-ΠΊΠΎΠΌΠΏΠ°ΡΠ°ΡΠΎΡΡ. ΠΡΠ΅ ΡΡΠΎ Π±ΠΎΠ»Π΅Π΅ Π°ΠΊΡΡΠ°Π»ΡΠ½ΠΎ Π΄Π»Ρ ΠΏΡΠΎΠΌΡΡΠ»Π΅Π½Π½ΠΎΠ³ΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°, Π½Π΅ΠΆΠ΅Π»ΠΈ Π΅Π³ΠΎ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ
ΠΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ Π΄ΠΎΡΡΡΠΏΠ½Ρ Π² Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ Π²ΠΈΠ΄Π°Ρ β ΡΡΠΈ Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΡ (Π³ΠΈΡΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΠΈΠ΄Π½ΠΎ ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠΊΠΎΡΠΎΡΡΠΈ ΠΏΡΠΈ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Π΅ ΠΊ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌΡ ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡ Π½Π° ΠΎΠ΄Π½ΠΎΠΌ ΡΠΈΠΏΠ΅ ΡΠ΅ΡΡΠΎΠ², Π³ΡΠ°ΡΠΈΠΊ, ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ°ΡΡΠΈΠΉ ΡΠΎ ΠΆΠ΅ ΡΠ°ΠΌΠΎΠ΅, Π½ΠΎ ΠΈΠ½ΠΎΠ³Π΄Π° Π±ΠΎΠ»Π΅Π΅ Π½Π°Π³Π»ΡΠ΄Π½ΠΎ, ΠΈ Π³ΠΈΡΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΠΈΠ΄Π½ΠΎ, ΠΊΠ°ΠΊΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π»ΡΡΡΠ΅ Π²ΡΠ΅Π³ΠΎ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π° ΠΊΠ°ΠΊΠΎΠΌ-ΡΠΎ ΡΠΈΠΏΠ΅ ΡΠ΅ΡΡΠΎΠ²) ΠΈ ΡΠ°Π±Π»ΠΈΡΡ, Π½Π° ΠΊΠΎΡΠΎΡΡΡ ΠΎΠ½ΠΈ ΠΎΡΠ½ΠΎΠ²Π°Π½Ρ. Π’ΡΠ΅ΡΡΡ Π³ΡΡΠΏΠΏΠ° Π±ΡΠ»Π° ΡΠ°Π·Π΄Π΅Π»Π΅Π½Π° Π΅ΡΠ΅ Π½Π° ΡΡΠΈ ΡΠ°ΡΡΠΈ, Π° ΡΠΎ ΠΌΠ°Π»ΠΎ ΡΡΠΎ Π±ΡΠ»ΠΎ Π±Ρ ΠΏΠΎΠ½ΡΡΠ½ΠΎ. ΠΠΏΡΠΎΡΠ΅ΠΌ, ΠΈ ΡΠ°ΠΊ Π΄Π°Π»Π΅ΠΊΠΎ Π½Π΅ Π²ΡΠ΅ Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΡ ΡΠ΄Π°ΡΠ½Ρ (Π² ΠΏΠΎΠ»Π΅Π·Π½ΠΎΡΡΠΈ ΡΡΠ΅ΡΡΠ΅Π³ΠΎ ΡΠΈΠΏΠ° Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌ Ρ Π²ΠΎΠΎΠ±ΡΠ΅ ΡΠΈΠ»ΡΠ½ΠΎ ΡΠΎΠΌΠ½Π΅Π²Π°ΡΡΡ), Π½ΠΎ, Π½Π°Π΄Π΅ΡΡΡ, ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠΌΠΎΠΆΠ΅Ρ Π½Π°ΠΉΡΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΡΡ Π΄Π»Ρ ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΡ.
ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΊΠ°ΡΡΠΈΠ½ΠΎΠΊ ΠΎΡΠ΅Π½Ρ ΠΌΠ½ΠΎΠ³ΠΎ, ΠΎΠ½ΠΈ ΡΠΊΡΡΡΡ ΡΠΏΠΎΠΉΠ»Π΅ΡΠ°ΠΌΠΈ. ΠΠ΅ΠΌΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠΌΠΌΠ΅Π½ΡΠ°ΡΠΈΠ΅Π² ΠΏΠΎ ΠΏΠΎΠ²ΠΎΠ΄Ρ ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΠΉ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π½Π°Π·Π²Π°Π½Ρ ΡΠ°ΠΊ, ΠΊΠ°ΠΊ Π²ΡΡΠ΅, Π΅ΡΠ»ΠΈ ΡΡΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π°, ΡΠΎ Π² ΡΠΊΠΎΠ±ΠΎΡΠΊΠ°Ρ ΡΠΊΠ°Π·Π°Π½ Π°Π²ΡΠΎΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ, ΠΊ Π½Π°Π·Π²Π°Π½ΠΈΡΠΌ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ, ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄ΡΡΠΈΡ Π½Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, ΠΏΡΠΈΠΏΠΈΡΠ°Π½ΠΎ Ins (Π΄Π»Ρ ΠΊΠΎΠΌΠΏΠ°ΠΊΡΠ½ΠΎΡΡΠΈ). Π Π΄ΠΈΠ°Π³ΡΠ°ΠΌΠΌΠ°Ρ Ρ Π²ΡΠΎΡΠΎΠΉ Π³ΡΡΠΏΠΏΡ ΡΠ΅ΡΡΠΎΠ² ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½Π° Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Π°Ρ Π΄Π»ΠΈΠ½Π° ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΠΏΠΎΠ΄ΠΌΠ°ΡΡΠΈΠ²ΠΎΠ², Ρ ΡΡΠ΅ΡΡΠ΅ΠΉ Π³ΡΡΠΏΠΏΡ β ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ²ΠΎΠΏΠΎΠ², Ρ ΡΠ΅ΡΠ²Π΅ΡΡΠΎΠΉ β ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π·Π°ΠΌΠ΅Π½. ΠΠ±ΡΠΈΠΉ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΡΠ°ΡΡΡΠΈΡΡΠ²Π°Π»ΡΡ ΠΊΠ°ΠΊ ΡΡΠ΅Π΄Π½Π΅Π΅ ΠΏΠΎ ΡΠ΅ΡΡΡΠ΅ΠΌ Π³ΡΡΠΏΠΏΠ°ΠΌ.
ΠΠ΅ΡΠ²Π°Ρ Π³ΡΡΠΏΠΏΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ
ΠΠ°ΡΡΠΈΠ² ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ ΡΠΈΡΠ΅Π»




Π‘ΠΎΠ²ΡΠ΅ΠΌ ΡΠΊΡΡΠ½ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ, Π΄Π°ΠΆΠ΅ ΡΠ°ΡΡΠΈΡΠ½Π°Ρ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΡ ΠΏΡΠΈ Π½Π΅Π±ΠΎΠ»ΡΡΠΎΠΌ ΠΌΠΎΠ΄ΡΠ»Π΅ ΠΏΠΎΡΡΠΈ Π½Π΅Π·Π°ΠΌΠ΅ΡΠ½Π°.
Π§Π°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ²



Π£ΠΆΠ΅ Π³ΠΎΡΠ°Π·Π΄ΠΎ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½Π΅Π΅. ΠΠ±ΠΌΠ΅Π½Π½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π½Π°ΠΈΠ±ΠΎΠ»Π΅Π΅ Π±ΡΡΠ½ΠΎ ΠΎΡΡΠ΅Π°Π³ΠΈΡΠΎΠ²Π°Π»ΠΈ, ΡΠ΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ Π΄Π°ΠΆΠ΅ ΠΎΠ±ΠΎΠ³Π½Π°Π»Π° Π³Π½ΠΎΠΌΡΡ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ ΡΡΠΊΠΎΡΠΈΠ»Π°ΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΠ΄ ΡΠ°ΠΌΡΠΉ ΠΊΠΎΠ½Π΅Ρ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ, ΠΊΠΎΠ½Π΅ΡΠ½ΠΎ, ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠΎΠ²Π΅ΡΡΠ΅Π½Π½ΠΎ ΡΠ°ΠΊΠΆΠ΅.
Π‘Π²ΠΎΠΏΡ




ΠΠ΄Π΅ΡΡ Π½Π°ΠΊΠΎΠ½Π΅Ρ-ΡΠΎ ΠΏΡΠΎΡΠ²ΠΈΠ»Π° ΡΠ΅Π±Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, Ρ ΠΎΡΡ ΡΠΎΡΡ ΡΠΊΠΎΡΠΎΡΡΠΈ Ρ ΡΠ΅ΠΉΠΊΠ΅ΡΠ½ΠΎΠΉ ΠΏΡΠΈΠΌΠ΅ΡΠ½ΠΎ ΡΠ°ΠΊΠΎΠΉ ΠΆΠ΅. ΠΠ΄Π΅ΡΡ ΠΏΡΠΎΡΠ²ΠΈΠ»Π°ΡΡ ΡΠ»Π°Π±ΠΎΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ β Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΡΠ²ΠΎΠΏΠ°, ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°ΡΡΠ΅Π³ΠΎ ΠΌΠ°Π»Π΅Π½ΡΠΊΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π² ΠΊΠΎΠ½Π΅Ρ, ΠΈ ΠΎΠ½Π° ΡΠΆΠ΅ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΠΌΠ΅Π΄Π»Π΅Π½Π½ΠΎ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ ΠΎΠΊΠ°Π·Π°Π»Π°ΡΡ ΠΏΠΎΡΡΠΈ Π² ΠΊΠΎΠ½ΡΠ΅.
ΠΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅




ΠΡΡΠΏΠΏΠ° ΠΏΠΎΡΡΠΈ Π½ΠΈΡΠ΅ΠΌ Π½Π΅ ΠΎΡΠ»ΠΈΡΠ°Π΅ΡΡΡ ΠΎΡ ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΉ, ΠΏΠΎΡΡΠΎΠΌΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ ΠΏΠΎΡ ΠΎΠΆΠΈ. ΠΠ΄Π½Π°ΠΊΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΏΡΠ·ΡΡΡΠΊΠΎΠΌ Π²ΡΡΡΠ²Π°Π΅ΡΡΡ Π²ΠΏΠ΅ΡΠ΅Π΄, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ, Π²ΡΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π² ΠΌΠ°ΡΡΠΈΠ², ΡΠΊΠΎΡΠ΅Π΅ Π²ΡΠ΅Π³ΠΎ Π±ΡΠ΄Π΅Ρ Π±ΠΎΠ»ΡΡΠ΅ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ , ΡΠΎ Π΅ΡΡΡ Π·Π° ΠΎΠ΄Π½Ρ ΠΈΡΠ΅ΡΠ°ΡΠΈΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΡΠΈΡΡΡ Π² ΠΊΠΎΠ½Π΅Ρ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ ΡΡΠ°Π»Π° Π°ΡΡΡΠ°ΠΉΠ΄Π΅ΡΠΎΠΌ.
ΠΠΎΠ²ΡΠΎΡΡ




ΠΠ΄Π΅ΡΡ Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ (ΠΊΡΠΎΠΌΠ΅, ΠΊΠΎΠ½Π΅ΡΠ½ΠΎ, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΠ±ΠΎΡΠΎΠΌ) ΡΠ°Π±ΠΎΡΠ°Π»ΠΈ ΠΏΠΎΡΡΠΈ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎ, ΡΡΠΊΠΎΡΡΡΡΡ ΠΏΠΎ ΠΌΠ΅ΡΠ΅ ΡΠ²Π΅Π»ΠΈΡΠ΅Π½ΠΈΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΏΠΎΠ²ΡΠΎΡΠΎΠ².
ΠΡΠΎΠ³ΠΎΠ²ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ
ΠΠ° ΡΡΠ΅Ρ ΡΠ²ΠΎΠ΅Π³ΠΎ Π°Π±ΡΠΎΠ»ΡΡΠ½ΠΎΠ³ΠΎ Π±Π΅Π·ΡΠ°Π·Π»ΠΈΡΠΈΡ ΠΊ ΠΌΠ°ΡΡΠΈΠ²Ρ, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΠ±ΠΎΡΠΎΠΌ, ΡΠ°Π±ΠΎΡΠ°Π²ΡΠ°Ρ Π±ΡΡΡΡΠ΅Π΅ Π²ΡΠ΅Ρ Π½Π° ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ Π΄Π°Π½Π½ΡΡ , Π²ΡΠ΅ ΠΆΠ΅ ΠΏΡΠΎΠΈΠ³ΡΠ°Π»Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ. ΠΠ½ΠΎΠΌΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΎΠΊΠ°Π·Π°Π»Π°ΡΡ Π·Π°ΠΌΠ΅ΡΠ½ΠΎ Ρ ΡΠΆΠ΅ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΉ, ΠΈΠ·-Π·Π° ΡΠ΅Π³ΠΎ Π΅Π΅ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠΎΠΌΠ½ΠΈΡΠ΅Π»ΡΠ½ΠΎ. Π¨Π΅ΠΉΠΊΠ΅ΡΠ½Π°Ρ ΠΈ ΠΏΡΠ·ΡΡΡΠΊΠΎΠ²Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΎΠΊΠ°Π·Π°Π»ΠΈΡΡ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ Π²ΡΠ΅Ρ .
ΠΡΠΎΡΠ°Ρ Π³ΡΡΠΏΠΏΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ
ΠΠ°ΡΡΠΈΠ² ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ ΡΠΈΡΠ΅Π»




Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π° Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡΡ ΠΡΠ°ΡΡΠ° Π²Π΅Π΄Π΅Ρ ΡΠ΅Π±Ρ ΡΠΎΠ²ΡΠ΅ΠΌ ΡΡΡΠ°Π½Π½ΠΎ, ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ Π±ΠΎΠ»Π΅Π΅ ΠΌΠ΅Π½Π΅Π΅ ΡΡΠ½ΠΎ. Π‘ΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ Π»ΡΠ±ΠΈΡ ΡΠ°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ, Π½ΠΎ Π½Π΅ Π»ΡΠ±ΠΈΡ ΠΏΠΎΠ²ΡΠΎΡΠΎΠ², Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΠΏΠΎΡΡΠΎΠΌΡ ΡΠ°ΠΌΠΎΠ΅ Ρ ΡΠ΄ΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ ΠΈΠΌΠ΅Π½Π½ΠΎ ΠΏΠΎΡΠ΅ΡΠ΅Π΄ΠΈΠ½Π΅.




ΠΡΠ΅ ΠΊΠ°ΠΊ ΠΏΡΠ΅ΠΆΠ΄Π΅, ΡΠΎΠ»ΡΠΊΠΎ Π¨Π΅Π»Π» Ρ ΠΡΠ°ΡΡΠΎΠΌ ΡΡΠΈΠ»ΠΈΠ»ΡΡ Π½Π° Π²ΡΠΎΡΠΎΠΉ Π³ΡΡΠΏΠΏΠ΅ ΠΈΠ·-Π·Π° ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΠΈ. Π’Π°ΠΊΠΆΠ΅ ΡΡΠ°Π½ΠΎΠ²ΠΈΡΡΡ Π·Π°ΠΌΠ΅ΡΠ½ΡΠΌ Π²Π»ΠΈΡΠ½ΠΈΠ΅ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠΈ β ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π° Π²ΡΠΎΡΠΎΠΌ ΠΌΠ΅ΡΡΠ΅, Π² ΠΎΡΠ»ΠΈΡΠΈΠ΅ ΠΎΡ Π³ΡΡΠΏΠΏΡ Ρ ΠΌΠ΅Π½ΡΡΠΈΠΌ ΡΠΈΡΠ»ΠΎΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
Π§Π°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ²



ΠΠ΄Π΅ΡΡ ΠΏΠΎΠ½ΡΡΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π²Π΅Π΄ΡΡ ΡΠ΅Π±Ρ Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΊΡΠΎΠΌΠ΅ Π¨Π΅Π»Π»Π° Ρ Π₯ΠΈΠ±Π±Π°ΡΠ΄ΠΎΠΌ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΡΠ΅ΠΌΡ-ΡΠΎ Π½Π΅ ΡΡΠ°Π·Ρ Π½Π°ΡΠΈΠ½Π°Π΅Ρ ΡΡΠΊΠΎΡΡΡΡΡΡ.




ΠΠ΄Π΅ΡΡ Π²ΡΠ΅, Π² ΠΎΠ±ΡΠ΅ΠΌ, ΠΊΠ°ΠΊ ΠΈ ΠΏΡΠ΅ΠΆΠ΄Π΅. ΠΠ°ΠΆΠ΅ Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π΄Π΅ΡΠ΅Π²ΠΎΠΌ Π½Π΅ ΠΏΠΎΠΌΠΎΠ³Π»Π° Π΅ΠΉ Π²ΡΡΠ²Π°ΡΡΡΡ Ρ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅Π³ΠΎ ΠΌΠ΅ΡΡΠ°.
Π‘Π²ΠΎΠΏΡ








ΠΠ΄Π΅ΡΡ Π·Π°ΠΌΠ΅ΡΠ½ΠΎ, ΡΡΠΎ Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ Π¨Π΅Π»Π»Π° Π±ΠΎΠ»ΡΡΠ°Ρ Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΡ ΠΎΡ ΡΠ°ΡΡΠΈΡΠ½ΠΎΠΉ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΠΈ, ΡΠ°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ Π²Π΅Π΄ΡΡ ΡΠ΅Π±Ρ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ, Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ Π΄Π²Π΅ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΈΠ»ΡΠ½ΠΎ ΠΏΠ°Π΄Π°ΡΡ Π½Π° ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΡ Π³ΡΡΠΏΠΏΠ°Ρ .
ΠΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅








ΠΠ΄Π΅ΡΡ Π²ΡΠ΅ ΠΏΠΎΡ ΠΎΠΆΠ΅ Π½Π° ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΡΡ Π³ΡΡΠΏΠΏΡ.
ΠΠΎΠ²ΡΠΎΡΡ




ΠΠΏΡΡΡ Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΎΠ΄Π΅ΠΌΠΎΠ½ΡΡΡΠΈΡΠΎΠ²Π°Π»ΠΈ ΡΠ΄ΠΈΠ²ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΡΠ±Π°Π»Π°Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΡ, Π΄Π°ΠΆΠ΅ Π±ΠΈΡΠΎΠ½Π½Π°Ρ, ΠΊΠΎΡΠΎΡΠ°Ρ, ΠΊΠ°Π·Π°Π»ΠΎΡΡ Π±Ρ, ΠΏΠΎΡΡΠΈ Π½Π΅ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΠΌΠ°ΡΡΠΈΠ²Π°.




ΠΡΠΎΠ³ΠΎΠ²ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ
Π£Π±Π΅Π΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΠΏΠ΅ΡΠ²ΠΎΠ΅ ΠΌΠ΅ΡΡΠΎ Π·Π°Π½ΡΠ»Π° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π° ΠΏΠΎ Π₯ΠΈΠ±Π±Π°ΡΠ΄Ρ, Π½Π΅ ΡΡΡΡΠΏΠΈΠ² Π½ΠΈ Π² ΠΎΠ΄Π½ΠΎΠΉ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠΉ Π³ΡΡΠΏΠΏΠ΅. ΠΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, ΡΡΠΎΠΈΠ»ΠΎ Π΅Π΅ ΠΎΡΠΏΡΠ°Π²ΠΈΡΡ Π² ΠΏΠ΅ΡΠ²ΡΡ Π³ΡΡΠΏΠΏΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ, Π½ΠΎβ¦ ΠΎΠ½Π° ΡΠ»ΠΈΡΠΊΠΎΠΌ ΡΠ»Π°Π±Π° Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ, Π΄Π° ΠΈ ΡΠΎΠ³Π΄Π° ΠΏΠΎΡΡΠΈ Π½ΠΈΠΊΠΎΠ³ΠΎ Π½Π΅ Π±ΡΠ»ΠΎ Π±Ρ Π² Π³ΡΡΠΏΠΏΠ΅. ΠΠΈΡΠΎΠ½Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΡΠ²Π΅ΡΠ΅Π½Π½ΠΎ Π·Π°Π½ΡΠ»Π° Π²ΡΠΎΡΠΎΠ΅ ΠΌΠ΅ΡΡΠΎ. Π’ΡΠ΅ΡΡΠ΅ ΠΌΠ΅ΡΡΠΎ ΠΏΡΠΈ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°Ρ Π·Π°Π½ΡΠ»Π° Π΄ΡΡΠ³Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π¨Π΅Π»Π»Π°, Π° ΠΏΡΠΈ Π΄Π΅ΡΡΡΠΈ ΠΌΠΈΠ»Π»ΠΈΠΎΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π΄Π΅ΡΠ΅Π²ΠΎΠΌ (Π°ΡΠΈΠΌΠΏΡΠΎΡΠΈΠΊΠ° ΡΠΊΠ°Π·Π°Π»Π°ΡΡ). Π‘ΡΠΎΠΈΡ ΠΎΠ±ΡΠ°ΡΠΈΡΡ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅, ΡΡΠΎ ΠΏΡΠΈ Π΄Π΅ΡΡΡΠΈΠΊΡΠ°ΡΠ½ΠΎΠΌ ΡΠ²Π΅Π»ΠΈΡΠ΅Π½ΠΈΠΈ ΡΠ°Π·ΠΌΠ΅ΡΠ° Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ Π²ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ, ΠΊΡΠΎΠΌΠ΅ Π΄ΡΠ΅Π²Π΅ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, Π·Π°ΠΌΠ΅Π΄Π»ΠΈΠ»ΠΈΡΡ ΠΏΠΎΡΡΠΈ Π² 20 ΡΠ°Π·, Π° ΠΏΠΎΡΠ»Π΅Π΄Π½ΡΡ Π²ΡΠ΅Π³ΠΎ Π»ΠΈΡΡ Π² 13.
Π’ΡΠ΅ΡΡΡ Π³ΡΡΠΏΠΏΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ
ΠΠ°ΡΡΠΈΠ² ΡΠ»ΡΡΠ°ΠΉΠ½ΡΡ ΡΠΈΡΠ΅Π»











ΠΠΎΡΡΠΈ Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΡΠΎΠΉ Π³ΡΡΠΏΠΏΡ ΠΈΠΌΠ΅ΡΡ ΠΏΠΎΡΡΠΈ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΡ Π΄ΠΈΠ½Π°ΠΌΠΈΠΊΡ. ΠΠΎΡΠ΅ΠΌΡ ΠΆΠ΅ ΠΏΠΎΡΡΠΈ Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΡΠΊΠΎΡΡΡΡΡΡ, ΠΊΠΎΠ³Π΄Π° ΠΌΠ°ΡΡΠΈΠ² ΡΠ°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½? ΠΠ±ΠΌΠ΅Π½Π½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π±ΡΡΡΡΠ΅Π΅ ΠΏΠΎΡΠΎΠΌΡ, ΡΡΠΎ Π½Π°Π΄ΠΎ Π΄Π΅Π»Π°ΡΡ ΠΌΠ΅Π½ΡΡΠ΅ ΠΎΠ±ΠΌΠ΅Π½ΠΎΠ², Π² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ Π¨Π΅Π»Π»Π° Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΠ°Ρ ΡΠΈΠ»ΡΠ½ΠΎ ΡΡΠΊΠΎΡΡΠ΅ΡΡΡ Π½Π° ΡΠ°ΠΊΠΈΡ ΠΌΠ°ΡΡΠΈΠ²Π°Ρ , Π² ΠΏΠΈΡΠ°ΠΌΠΈΠ΄Π°Π»ΡΠ½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ ΠΏΡΠΈ Π²ΡΡΠ°Π²ΠΊΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΡΡΠ°Π·Ρ Π·Π°Π²Π΅ΡΡΠ°Π΅ΡΡΡ ΠΏΡΠΎΡΠ΅ΠΈΠ²Π°Π½ΠΈΠ΅, Π² ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ΅ ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π² Π»ΡΡΡΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ Π²Π΄Π²ΠΎΠ΅ ΠΌΠ΅Π½ΡΡΠ΅ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ. ΠΠ»ΠΎΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠ΅ΠΌ Π»ΡΡΡΠ΅, ΡΠ΅ΠΌ ΠΌΠ΅Π½ΡΡΠ΅ ΡΠ°Π·Π½ΠΎΡΡΡ ΠΌΠ΅ΠΆΠ΄Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΈ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠΌ. ΠΡΠΈΠ½ΡΠΈΠΏΠΈΠ°Π»ΡΠ½ΠΎ ΠΎΡΠ»ΠΈΡΠ°Π΅ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΠΎΡΠ°Π·ΡΡΠ΄Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΡΠ΅ ΡΡΠΎ Π±Π΅Π·ΡΠ°Π·Π»ΠΈΡΠ½ΠΎ. LSD-Π²Π΅ΡΡΠΈΡ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠ΅ΠΌ Π»ΡΡΡΠ΅, ΡΠ΅ΠΌ Π±ΠΎΠ»ΡΡΠΈΠΉ ΠΌΠΎΠ΄ΡΠ»Ρ. ΠΠΈΠ½Π°ΠΌΠΈΠΊΠ° MSD-Π²Π΅ΡΡΠΈΡ ΠΌΠ½Π΅ Π½Π΅ ΡΡΠ½Π°, ΡΠΎ, ΡΡΠΎ ΠΎΠ½Π° ΡΡΠ°Π±ΠΎΡΠ°Π»Π° Π±ΡΡΡΡΠ΅Π΅ ΡΠ΅ΠΌ LSD ΡΠ΄ΠΈΠ²ΠΈΠ»ΠΎ.
Π§Π°ΡΡΠΈΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ²
ΠΠ΄Π΅ΡΡ Π²ΡΠ΅ ΡΠΎΠΆΠ΅ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΠΏΠΎΠ½ΡΡΠ½ΠΎ. Π‘ΡΠ°Π»ΠΎ Π·Π°ΠΌΠ΅ΡΠ΅Π½ Π°Π»Π³ΠΎΡΠΈΡΠΌ Timsort, Π½Π° Π½Π΅Π³ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΡ Π΄Π΅ΠΉΡΡΠ²ΡΠ΅Ρ ΡΠΈΠ»ΡΠ½Π΅Π΅, ΡΠ΅ΠΌ Π½Π° ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅. ΠΡΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ»ΠΎ ΡΡΠΎΠΌΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΏΠΎΡΡΠΈ ΡΡΠ°Π²Π½ΡΡΡΡΡ Ρ ΠΎΠΏΡΠΈΠΌΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ΅ΠΉ Π±ΡΡΡΡΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΠ»ΠΎΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°, Π½Π΅ΡΠΌΠΎΡΡΡ Π½Π° ΡΠ»ΡΡΡΠ΅Π½ΠΈΠ΅ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΈ ΡΠ°ΡΡΠΈΡΠ½ΠΎΠΉ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΡΡΠΈ, Π½Π΅ ΡΠΌΠΎΠ³Π»Π° ΠΎΠ±ΠΎΠ³Π½Π°ΡΡ ΠΏΠΎΡΠ°Π·ΡΡΠ΄Π½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ.
Π‘Π²ΠΎΠΏΡ
ΠΠ΄Π΅ΡΡ ΠΎΡΠ΅Π½Ρ Ρ ΠΎΡΠΎΡΠΎ ΡΡΠ°Π±ΠΎΡΠ°Π»ΠΈ Π±ΡΡΡΡΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ. ΠΡΠΎ, ΡΠΊΠΎΡΠ΅Π΅ Π²ΡΠ΅Π³ΠΎ, ΠΎΠ±ΡΡΡΠ½ΡΠ΅ΡΡΡ ΡΠ΄Π°ΡΠ½ΡΠΌ Π²ΡΠ±ΠΎΡΠΎΠΌ ΠΎΠΏΠΎΡΠ½ΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°. ΠΡΠ΅ ΠΎΡΡΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΠΎΡΡΠΈ ΡΠ°ΠΊΠΆΠ΅, ΠΊΠ°ΠΊ ΠΈ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΉ Π³ΡΡΠΏΠΏΠ΅.
ΠΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠ΅
ΠΠ½Π΅ ΡΠ΄Π°Π»ΠΎΡΡ Π΄ΠΎΡΡΠΈΡΡ ΠΆΠ΅Π»Π°Π΅ΠΌΠΎΠΉ ΡΠ΅Π»ΠΈ β ΠΏΠΎΡΠ°Π·ΡΡΠ΄Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠΏΠ°Π»Π° Π΄Π°ΠΆΠ΅ Π½ΠΈΠΆΠ΅ Π°Π΄Π°ΠΏΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ Π±ΡΡΡΡΠΎΠΉ. ΠΠ»ΠΎΡΠ½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΎΠΊΠ°Π·Π°Π»Π°ΡΡ Π»ΡΡΡΠ΅ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ . ΠΡΠ΅ ΠΏΠΎΡΠ΅ΠΌΡ-ΡΠΎ timsort ΠΎΠ±ΠΎΠ³Π½Π°Π» Π²ΡΡΡΠΎΠ΅Π½Π½ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ C++, Ρ ΠΎΡΡ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΉ Π³ΡΡΠΏΠΏΠ΅ Π±ΡΠ» Π½ΠΈΠΆΠ΅.
ΠΠΎΠ²ΡΠΎΡΡ
ΠΠ΄Π΅ΡΡ Π²ΡΠ΅ Π΄ΠΎΠ²ΠΎΠ»ΡΠ½ΠΎ ΡΠΎΡΠΊΠ»ΠΈΠ²ΠΎ, Π²ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΡΠ°Π±ΠΎΡΠ°ΡΡ Ρ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΠΊΠΎΠΉ (ΠΊΡΠΎΠΌΠ΅ Π»ΠΈΠ½Π΅ΠΉΠ½ΡΡ ). ΠΠ· Π½Π΅ΠΎΠ±ΡΡΠ½ΠΎΠ³ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π·Π°ΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΡΠ»ΠΈΡΠ½ΠΈΠ΅ΠΌ ΡΠΏΠ°Π»Π° Π½ΠΈΠΆΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π¨Π΅Π»Π»Π°.
ΠΡΠΎΠ³ΠΎΠ²ΡΠ΅ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ
ΠΡΠ»ΠΈ Π³ΠΎΠ²ΠΎΡΠΈΡΡ ΠΎ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠΈ, ΡΠΎ Ρ ΠΎΡΠΎΡΠ° ΠΏΠΎΡΠ°Π·ΡΡΠ΄Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° (ΠΎΡΠΎΠ±Π΅Π½Π½ΠΎ lsd-Π²Π΅ΡΡΠΈΡ), ΠΎΠ½Π° ΡΡΠ°Π±ΠΈΠ»ΡΠ½Π°, ΠΏΡΠΎΡΡΠ° Π² ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΠΈ ΠΎΡΠ΅Π½Ρ Π±ΡΡΡΡΠ°, ΠΎΠ΄Π½Π°ΠΊΠΎ Π½Π΅ ΠΎΡΠ½ΠΎΠ²Π°Π½Π° Π½Π° ΡΡΠ°Π²Π½Π΅Π½ΠΈΡΡ . ΠΠ· ΠΎΡΠ½ΠΎΠ²Π°Π½Π½ΡΡ Π½Π° ΡΡΠ°Π²Π½Π΅Π½ΠΈΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΎΠΊ Π»ΡΡΡΠ΅ Π²ΡΠ΅Π³ΠΎ ΡΠΌΠΎΡΡΠΈΡΡΡ Π±ΡΡΡΡΠ°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ°. ΠΠ΅ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΊΠΈ β Π½Π΅ΡΡΡΠΎΠΉΡΠΈΠ²ΠΎΡΡΡ ΠΈ ΠΊΠ²Π°Π΄ΡΠ°ΡΠΈΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π½Π° Π½Π΅ΡΠ΄Π°ΡΠ½ΡΡ Π²Ρ ΠΎΠ΄Π½ΡΡ Π΄Π°Π½Π½ΡΡ (ΠΏΡΡΡΡ ΠΎΠ½ΠΈ ΠΈ ΠΌΠΎΠ³ΡΡ Π²ΡΡΡΠ΅ΡΠΈΡΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΠΏΡΠΈ Π½Π°ΠΌΠ΅ΡΠ΅Π½Π½ΠΎΠΌ ΡΠΎΠ·Π΄Π°Π½ΠΈΠΈ ΡΠ΅ΡΡΠ°). ΠΠΎ Ρ ΡΡΠΈΠΌ ΠΌΠΎΠΆΠ½ΠΎ Π±ΠΎΡΠΎΡΡΡΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π²ΡΠ±ΠΈΡΠ°Ρ ΠΎΠΏΠΎΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΏΠΎ ΠΊΠ°ΠΊΠΎΠΌΡ-Π½ΠΈΠ±ΡΠ΄Ρ Π΄ΡΡΠ³ΠΎΠΌΡ ΠΏΡΠΈΠ½ΡΠΈΠΏΡ, ΠΈΠ»ΠΈ ΠΆΠ΅ ΠΏΠ΅ΡΠ΅Ρ ΠΎΠ΄Ρ Π½Π° Π΄ΡΡΠ³ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΡ ΠΏΡΠΈ Π½Π΅ΡΠ΄Π°ΡΠ΅ (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, introsort, ΠΊΠΎΡΠΎΡΡΠΉ, Π΅ΡΠ»ΠΈ Π½Π΅ ΠΎΡΠΈΠ±Π°ΡΡΡ, ΠΈ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ Π² Π‘++). Timsort Π»ΠΈΡΠ΅Π½ ΡΡΠΈΡ Π½Π΅Π΄ΠΎΡΡΠ°ΡΠΊΠΎΠ², Π»ΡΡΡΠ΅ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ Π½Π° ΡΠΈΠ»ΡΠ½ΠΎ ΠΎΡΡΠΎΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π΄Π°Π½Π½ΡΡ , Π½ΠΎ Π²ΡΠ΅ ΠΆΠ΅ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ Π² ΡΠ΅Π»ΠΎΠΌ ΠΈ Π³ΠΎΡΠ°Π·Π΄ΠΎ ΡΠ»ΠΎΠΆΠ½Π΅Π΅ ΠΏΠΈΡΠ΅ΡΡΡ. ΠΡΡΠ°Π»ΡΠ½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π½Π° Π΄Π°Π½Π½ΡΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ, ΠΏΠΎΠΆΠ°Π»ΡΠΉ, Π½Π΅ ΠΎΡΠ΅Π½Ρ ΠΏΡΠ°ΠΊΡΠΈΡΠ½Ρ. ΠΡΠΎΠΌΠ΅, ΠΊΠΎΠ½Π΅ΡΠ½ΠΎ, ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π²ΡΡΠ°Π²ΠΊΠ°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΡ Π²Π΅ΡΡΠΌΠ° ΡΠ΄Π°ΡΠ½ΠΎ ΠΈΠ½ΠΎΠ³Π΄Π° ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΡΠ°Π²ΠΈΡΡ Π² Π°Π»Π³ΠΎΡΠΈΡΠΌ.
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
ΠΠΎΠ»ΠΆΠ΅Π½ ΠΎΡΠΌΠ΅ΡΠΈΡΡ, ΡΡΠΎ Π½Π΅ Π²ΡΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ½ΡΠ΅ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ ΠΏΡΠΈΠ½ΡΠ»ΠΈ ΡΡΠ°ΡΡΠΈΠ΅ Π² ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π±ΡΠ»Π° ΠΏΡΠΎΠΏΡΡΠ΅Π½Π° ΠΏΠ»Π°Π²Π½Π°Ρ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° (ΠΌΠ½Π΅ ΠΏΡΠΎΡΡΠΎ Π½Π΅ ΡΠ΄Π°Π»ΠΎΡΡ Π΅Π΅ Π°Π΄Π΅ΠΊΠ²Π°ΡΠ½ΠΎ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ). ΠΠΏΡΠΎΡΠ΅ΠΌ, Π½Π΅ Π΄ΡΠΌΠ°Ρ, ΡΡΠΎ ΡΡΠΎ Π±ΠΎΠ»ΡΡΠ°Ρ ΠΏΠΎΡΠ΅ΡΡ, ΡΡΠ° ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠ° ΠΎΡΠ΅Π½Ρ Π³ΡΠΎΠΌΠΎΠ·Π΄ΠΊΠ°Ρ ΠΈ ΠΌΠ΅Π΄Π»Π΅Π½Π½Π°Ρ, ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ½ΠΎ Π²ΠΈΠ΄Π΅ΡΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΈΠ· ΡΡΠΎΠΉ ΡΡΠ°ΡΡΠΈ: habrahabr.ru/post/133996 ΠΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΡ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ Π½Π° ΡΠ°ΡΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΠΈΠ²Π°Π½ΠΈΠ΅, Π½ΠΎ, Π²ΠΎ-ΠΏΠ΅ΡΠ²ΡΡ , Ρ ΠΌΠ΅Π½Ρ Π½Π΅Ρ ΠΎΠΏΡΡΠ°, Π²ΠΎ-Π²ΡΠΎΡΡΡ , ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ, ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΠΎΠ»ΡΡΠ°Π»ΠΈΡΡ, ΠΊΡΠ°ΠΉΠ½Π΅ Π½Π΅ΡΡΠ°Π±ΠΈΠ»ΡΠ½Ρ, ΠΎΡΠ΅Π½Ρ Π²Π΅Π»ΠΈΠΊΠΎ Π²Π»ΠΈΡΠ½ΠΈΠ΅ ΡΠΈΡΡΠ΅ΠΌΡ.
ΠΠ΄Π΅ΡΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΠΌΠΎΡΡΠ΅ΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ Π²ΡΠ΅Ρ Π·Π°ΠΏΡΡΠΊΠΎΠ², Π° ΡΠ°ΠΊΠΆΠ΅ Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°ΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ: ΡΡΡΠ»ΠΊΠ° Π½Π° Π΄ΠΎΠΊΡΠΌΠ΅Π½Ρ.
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Ρ Π²Π΅ΠΊΡΠΎΡΠ°ΠΌΠΈ ΠΎΡΡΠ°Π»ΠΈΡΡ, Π½ΠΎ ΠΈΡ ΠΊΠΎΡΡΠ΅ΠΊΡΠ½ΠΎΡΡΡ ΠΈ Ρ ΠΎΡΠΎΡΡΡ ΡΠ°Π±ΠΎΡΡ Π½Π΅ Π³Π°ΡΠ°Π½ΡΠΈΡΡΡ. ΠΡΠΎΡΠ΅ Π²Π·ΡΡΡ ΠΊΠΎΠ΄Ρ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΈΠ· ΡΡΠ°ΡΡΠΈ ΠΈ ΠΏΠ΅ΡΠ΅Π΄Π΅Π»Π°ΡΡ. ΠΠ΅Π½Π΅ΡΠ°ΡΠΎΡΡ ΡΠ΅ΡΡΠΎΠ² ΡΠΎΠΆΠ΅ ΠΌΠΎΠ³ΡΡ Π½Π΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ, Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ ΡΠ°ΠΊΠΎΠΉ Π²ΠΈΠ΄ ΠΎΠ½ΠΈ ΠΏΡΠΈΠ½ΡΠ»ΠΈ ΡΠΆΠ΅ ΠΏΠΎΡΠ»Π΅ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΡΠ΅ΡΡΠΎΠ², ΠΊΠΎΠ³Π΄Π° Π½ΡΠΆΠ½ΠΎ Π±ΡΠ»ΠΎ ΡΠ΄Π΅Π»Π°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π±ΠΎΠ»Π΅Π΅ ΠΊΠΎΠΌΠΏΠ°ΠΊΡΠ½ΠΎΠΉ.
Π ΠΎΠ±ΡΠ΅ΠΌ, Ρ Π΄ΠΎΠ²ΠΎΠ»Π΅Π½ ΠΏΡΠΎΠ΄Π΅Π»Π°Π½Π½ΠΎΠΉ ΡΠ°Π±ΠΎΡΠΎΠΉ, Π½Π°Π΄Π΅ΡΡΡ, ΡΡΠΎ ΠΠ°ΠΌ Π±ΡΠ»ΠΎ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΠΎ.
























































































































