nikita.kopot 08 фСвраля 2022

πŸš„ Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ 6 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки: ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ, Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ, ΠΊΡƒΡ‡Π΅ΠΉ, вставками, слияниСм ΠΈ быстрая

Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ Π½Π°Ρ‡Π½Π΅ΠΌ ΠΈΠ·ΡƒΡ‡Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки, Ρ€Π°Π·Π±Π΅Ρ€Π΅ΠΌ 6 ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² сортировки ΠΈ ознакомимся с ΠΎΡ†Π΅Π½ΠΊΠΎΠΉ ΠΈΡ… эффСктивности.
πŸš„ Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ 6 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки: ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ, Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ, ΠΊΡƒΡ‡Π΅ΠΉ, вставками, слияниСм ΠΈ быстрая

Если Ρ…ΠΎΡ‡Π΅ΡˆΡŒ ΠΏΠΎΠ΄Ρ‚ΡΠ½ΡƒΡ‚ΡŒ свои знания, загляни Π½Π° наш курс «Алгоритмы ΠΈ структуры Π΄Π°Π½Π½Ρ‹Ρ…Β», Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Ρ‚Ρ‹:

  1. ΡƒΠ³Π»ΡƒΠ±ΠΈΡˆΡŒΡΡ Π² Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ практичСских Π·Π°Π΄Π°Ρ‡;
  2. ΡƒΠ·Π½Π°Π΅ΡˆΡŒ всС ΠΏΡ€ΠΎ слоТныС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹, сортировки, сТатиС Π΄Π°Π½Π½Ρ‹Ρ… ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠ΅ Π΄Ρ€ΡƒΠ³ΠΎΠ΅.

Π’Ρ‹ Ρ‚Π°ΠΊΠΆΠ΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π½Π° связи с ΠΏΡ€Π΅ΠΏΠΎΠ΄Π°Π²Π°Ρ‚Π΅Π»Π΅ΠΌ ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΠΌΠΈ студСнтами.

Π’ ΠΈΡ‚ΠΎΠ³Π΅ Π±ΡƒΠ΄Π΅ΡˆΡŒ Π±Ρ€Π°Ρ‚ΡŒΡΡ Π·Π° слоТныС ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Ρ‹ ΠΈ ΠΏΠΎΠ²Ρ‹ΡΠΈΡˆΡŒ Ρ‡Π΅ΠΊ Π·Π° свою Ρ€Π°Π±ΠΎΡ‚Ρƒ πŸ™‚

ВсС Π»ΡŽΠ±ΡΡ‚, ΠΊΠΎΠ³Π΄Π° Π΄Π°Π½Π½Ρ‹Π΅ отсортированы. Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° позволяСт ΡƒΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡ΠΈΠ²Π°Ρ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅ Π² Π½ΡƒΠΆΠ½ΠΎΠΉ Π½Π°ΠΌ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. Π’ порядкС возрастания ΠΈ убывания. ΠŸΡ€Π΅Π΄ΡΡ‚Π°Π²ΡŒΡ‚Π΅, Ρ‡Ρ‚ΠΎ Π²Ρ‹ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚Π΅ Π² ΠΊΡ€ΡƒΠΏΠ½ΠΎΠΉ ΠΊΠΎΠΌΠΏΠ°Π½ΠΈΠΈ ΠΈ Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΎΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΠΌΠ΅Π½Π° Ρ€Π°Π±ΠΎΡ‚Π½ΠΈΠΊΠΎΠ² Π² зависимости ΠΎΡ‚ ΠΈΡ… Π·Π°Ρ€ΠΏΠ»Π°Ρ‚Ρ‹. Для этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сортировки.

БСгодня ΠΌΡ‹ рассмотрим основныС Π²ΠΈΠ΄Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки. Но спСрва проясним, Ρ‡Ρ‚ΠΎ ΠΈΠ· сСбя прСдставляСт сортировочный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ.

Π§Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сортировки?

Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° Π±ΠΎΠ»ΡŒΡˆΠΈΡ… объСмов Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΡ‚Π½ΠΈΠΌΠ°Π΅Ρ‚ ΠΌΠ½ΠΎΠ³ΠΎ сил ΠΈ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ. Алгоритмы сортировки, ΠΊΠ°ΠΊ ΡƒΠΏΠΎΠΌΠΈΠ½Π°Π»ΠΎΡΡŒ Ρ€Π°Π½Π΅Π΅, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ ΠΎΠ±Π»Π΅Π³Ρ‡ΠΈΡ‚ΡŒ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ этой Π·Π°Π΄Π°Ρ‡ΠΈ.

Алгоритмы сортировки ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ ΡƒΠΏΠΎΡ€ΡΠ΄ΠΎΡ‡ΠΈΡ‚ΡŒ Π·Π°Π΄Π°Π½Π½Ρ‹Π΅ списки ΠΈ массивы Π΄Π°Π½Π½Ρ‹Ρ… с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² сравнСния. Π­Ρ‚ΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Ρ‹ ΠΏΡ€ΠΈΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ ΠΊ элСмСнтам массива ΠΈ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‚ ΠΈΡ… ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Π² структурС Π΄Π°Π½Π½Ρ‹Ρ….

К ΠΏΡ€ΠΈΠΌΠ΅Ρ€Ρƒ, символы Π½ΠΈΠΆΠ΅ ΠΈΠ΄ΡƒΡ‚ Π² порядкС возрастания согласно ΠΊΠΎΠ΄ΠΈΡ€ΠΎΠ²ΠΊΠ΅ ASCII. Π’ процСссС сортировки ΠΈΠ΄Π΅Ρ‚ сравнСниС элСмСнтов ΠΌΠ΅ΠΆΠ΄Ρƒ собой. Π§Π΅ΠΌ Π²Ρ‹ΡˆΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ символа Π² Ρ‚Π°Π±Π»ΠΈΡ†Π΅ ASCII, Ρ‚Π΅ΠΌ дальшС ΠΎΡ‚ Π½Π°Ρ‡Π°Π»Π° списка ΠΎΠ½ Π±ΡƒΠ΄Π΅Ρ‚ располоТСн.

πŸš„ Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ 6 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки: ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ, Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ, ΠΊΡƒΡ‡Π΅ΠΉ, вставками, слияниСм ΠΈ быстрая

КакиС ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сортировки?

БущСствуСт мноТСство Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ². БСгодня ΠΌΡ‹ рассмотрим 6 ΠΈΠ· Π½ΠΈΡ….

Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ Один ΠΈΠ· ΠΏΡ€ΠΎΡΡ‚Π΅ΠΉΡˆΠΈΡ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² сортировки. Π—Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² постСпСнном смСщСнии элСмСнтов с большим Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ Π² ΠΊΠΎΠ½Π΅Ρ† массива. Π­Π»Π΅ΠΌΠ΅Π½Ρ‚Ρ‹ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ ΡΡ€Π°Π²Π½ΠΈΠ²Π°ΡŽΡ‚ΡΡ ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ, ΠΈ Ссли порядок Π² ΠΏΠ°Ρ€Π΅ Π½Π°Ρ€ΡƒΡˆΠ΅Π½ – ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ мСстами.
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ Алгоритм ΠΈΡ‰Π΅Ρ‚ наимСньший элСмСнт Π² Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΌ спискС ΠΈ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚ ΠΎΠ±ΠΌΠ΅Π½ Π΅Π³ΠΎ значСния со Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ ΠΏΠ΅Ρ€Π²ΠΎΠΉ нСотсортированной ΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ. Π’ΠΎ ΠΆΠ΅ самоС происходит со Π²Ρ‚ΠΎΡ€Ρ‹ΠΌ элСмСнтом с наимСньшим Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ. Π¦ΠΈΠΊΠ» повторяСтся Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° всС элСмСнты Π½Π΅ Π·Π°ΠΉΠΌΡƒΡ‚ Π½ΡƒΠΆΠ½ΡƒΡŽ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ.
Быстрая сортировка БчитаСтся ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ· самых быстрых Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки. Как ΠΈ сортировка слияниСм, Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ ΠΏΠΎ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡƒ «раздСляй ΠΈ властвуй». ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ‚ Π΄ΠΎΡΡ‚ΠΈΠ³Π°Ρ‚ΡŒ O(n log n).
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΊΡƒΡ‡Π΅ΠΉ (ΠŸΠΈΡ€Π°ΠΌΠΈΠ΄Π°Π»ΡŒΠ½Π°Ρ сортировка) Алгоритм выстраиваСт Π΄Π°Π½Π½Ρ‹Π΅ Π² Π²ΠΈΠ΄Π΅ Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠ³ΠΎ Π΄Π΅Ρ€Π΅Π²Π° (Π΄Π²ΠΎΠΈΡ‡Π½ΠΎΠΉ ΠΊΡƒΡ‡ΠΈ). БущСствуСт Π΄Π²Π° Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Π° располоТСния элСмСнтов – max-heap (Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ родитСля большС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠΎΡ‚ΠΎΠΌΠΊΠΎΠ²) ΠΈ min-heap (Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ родитСля мСньшС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΏΠΎΡ‚ΠΎΠΌΠΊΠΎΠ²). Наибольший / наимСньший элСмСнт (Π² зависимости ΠΎΡ‚ Ρ‚ΠΈΠΏΠ°) располагаСтся Π² ΠΊΠΎΡ€Π½Π΅ Π΄Π΅Ρ€Π΅Π²Π°. Он мСняСтся мСстами с послСдним элСмСнтом ΠΊΡƒΡ‡ΠΈ ΠΈ помСщаСтся Π² ΠΊΠΎΠ½Π΅Ρ† массива. Π Π°Π·ΠΌΠ΅Ρ€ ΠΊΡƒΡ‡ΠΈ ΡƒΠΌΠ΅Π½ΡŒΡˆΠ°Π΅Ρ‚ΡΡ Π½Π° 1, послС Ρ‡Π΅Π³ΠΎ ΠΎΠ½Π° пСрСстраиваСтся. Π¦ΠΈΠΊΠ» повторяСтся, ΠΏΠΎΠΊΠ° Ρ€Π°Π·ΠΌΠ΅Ρ€ ΠΊΡƒΡ‡ΠΈ большС 1.
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставками ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΠ΅Ρ‚ΡΡ для вставки элСмСнтов массива Π½Π° «своС мСсто». Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставками прСдставляСт собой простой ΠΌΠ΅Ρ‚ΠΎΠ΄ сортировки ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для раскладки ΠΊΠΎΠ»ΠΎΠ΄Ρ‹ Π²ΠΎ врСмя ΠΈΠ³Ρ€Ρ‹ Π² Π±Ρ€ΠΈΠ΄ΠΆ.
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° слияниСм Π‘Π»Π΅Π΄ΡƒΠ΅Ρ‚ ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΡƒ «раздСляй ΠΈ властвуй», согласно ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ массив Π΄Π°Π½Π½Ρ‹Ρ… раздСляСтся Π½Π° Ρ€Π°Π²Π½Ρ‹Π΅ части, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΡΠΎΡ€Ρ‚ΠΈΡ€ΡƒΡŽΡ‚ΡΡ ΠΏΠΎ-ΠΎΡ‚Π΄Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ. ПослС ΠΎΠ½ΠΈ ΡΠ»ΠΈΠ²Π°ΡŽΡ‚ΡΡ, Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ получаСтся отсортированный массив.

Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ°, Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ элСмСнтов Π½Π΅ измСнилась, называСтся устойчивой.

πŸš„ Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ 6 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки: ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ, Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ, ΠΊΡƒΡ‡Π΅ΠΉ, вставками, слияниСм ΠΈ быстрая

ΠŸΡ€ΠΈ нСустойчивой сортировкС элСмСнты Π² массивС ΠΌΠ΅Π½ΡΡŽΡ‚ΡΡ мСстами.

πŸš„ Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ 6 Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки: ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ, Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ, ΠΊΡƒΡ‡Π΅ΠΉ, вставками, слияниСм ΠΈ быстрая

КакиС Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ сортировки ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΠ²Π°ΡŽΡ‚ ΡΡ‚Π°Π±ΠΈΠ»ΡŒΠ½ΠΎΡΡ‚ΡŒ?

Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ Π½ΠΈΠΆΠ΅ прСдставлСна ΡΡ‚Π°Π±ΠΈΠ»ΡŒΠ½ΠΎΡΡ‚ΡŒ рассмотрСнных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки

Алгоритм сортировки Π‘Ρ‚Π°Π±ΠΈΠ»ΡŒΠ½ΠΎΡΡ‚ΡŒ
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ βœ“
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ ✘
Быстрая сортировка ✘
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΊΡƒΡ‡Π΅ΠΉ ✘
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставками βœ“
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° слияниСм βœ“

МоТно Π»ΠΈ ΠΎΡ†Π΅Π½ΠΈΡ‚ΡŒ ΡΡ„Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² сортировки?

Π”Π°, это Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.

ΠšΡ€ΠΈΡ‚Π΅Ρ€ΠΈΡΠΌΠΈ ΠΎΡ†Π΅Π½ΠΊΠΈ эффСктивности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° сортировки являСтся пространствСнная ΠΈ врСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ.

ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠžΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ количСство памяти, Π·Π°Ρ‚Ρ€Π°Ρ‡Π΅Π½Π½ΠΎΠΉ Π½Π° Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½ΡƒΡŽ ΠΏΠ°ΠΌΡΡ‚ΡŒ ΠΈ ΠΏΠ°ΠΌΡΡ‚ΡŒ для хранСния Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ….

Π’ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Π°Ρ ΠΏΠ°ΠΌΡΡ‚ΡŒ – Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ мСсто, Π·Π°Π½ΠΈΠΌΠ°Π΅ΠΌΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ ΠΏΠΎΠΌΠΈΠΌΠΎ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. Она учитываСтся ΠΏΡ€ΠΈ расчСтС пространствСнной слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ².

ВрСмСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ

ΠžΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ врСмя, Π·Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ выполняСт ΠΏΠΎΡΡ‚Π°Π²Π»Π΅Π½Π½ΡƒΡŽ Π·Π°Π΄Π°Ρ‡Ρƒ с ΡƒΡ‡Π΅Ρ‚ΠΎΠΌ Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ…. ΠœΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½Π° с использованиСм ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΡ… Π½ΠΎΡ‚Π°Ρ†ΠΈΠΉ:

  1. Нотация «ОмСга» (Ξ©)
  2. Нотация Β«OΒ» большоС (O)
  3. Нотация Β«Π’Π΅Ρ‚Π°Β» (Θ)

Π’ Ρ‚Π°Π±Π»ΠΈΡ†Π΅ прСдставлСна ΠΎΡ†Π΅Π½ΠΊΠ° слоТности Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ², упомянутых Ρ€Π°Π½Π΅Π΅

Алгоритм сортировки ВрСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π² Ρ…ΡƒΠ΄ΡˆΠ΅ΠΌ случаС ВрСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π² срСднСм случаС ВрСмя Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π² Π»ΡƒΡ‡ΡˆΠ΅ΠΌ случаС ΠŸΡ€ΠΎΡΡ‚Ρ€Π°Π½ΡΡ‚Π²Π΅Π½Π½Π°Ρ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΏΡƒΠ·Ρ‹Ρ€ΡŒΠΊΠΎΠΌ n^2 n^2 n 1
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ n^2 n^2 n^2 1
Быстрая сортировка n^2 nlog n nlog n nlog n
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° ΠΊΡƒΡ‡Π΅ΠΉ nlog n nlog n nlog n 1
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° вставками n^2 n^2 n 1
Π‘ΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²ΠΊΠ° слияниСм nlog n nlog n nlog n n
***

Π£ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° сортировки своя врСмСнная ΠΈ пространствСнная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ. Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΌΠΎΠΆΠ½ΠΎ любой ΠΈΠ· прСдставлСнных Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π² зависимости ΠΎΡ‚ поставлСнных Π·Π°Π΄Π°Ρ‡. Но ΠΏΠΎ ΠΌΠΎΠ΅ΠΌΡƒ ΡΡƒΠ±ΡŠΠ΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΠΌΡƒ мнСнию Π»ΡƒΡ‡ΡˆΠΈΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ являСтся быстрая сортировка. Она позволяСт Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ ΠΎΠΏΠΎΡ€Π½Ρ‹ΠΉ элСмСнт ΠΈ раздСляСт массив Π½Π° 3 части: мСньшС, Ρ€Π°Π²Π½ΠΎ ΠΈ большС ΠΎΠΏΠΎΡ€Π½ΠΎΠ³ΠΎ элСмСнта.

Π‘ΠΎΠ»ΡŒΡˆΠ΅ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΠΉ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ Π²Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π½Π°ΠΉΡ‚ΠΈ Π½Π° нашСм Ρ‚Π΅Π»Π΅Π³Ρ€Π°ΠΌ-ΠΊΠ°Π½Π°Π»Π΅ Β«Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠ° программиста»

ΠœΠ°Ρ‚Π΅Ρ€ΠΈΠ°Π»Ρ‹ ΠΏΠΎ Ρ‚Π΅ΠΌΠ΅

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊΠΈ

ΠœΠ•Π ΠžΠŸΠ Π˜Π―Π’Π˜Π―

ΠšΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΈ

Π’ΠΠšΠΠΠ‘Π˜Π˜

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ вакансию
Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊ C++
Москва, ΠΏΠΎ ΠΈΡ‚ΠΎΠ³Π°ΠΌ собСсСдования

Π›Π£Π§Π¨Π˜Π• БВАВЬИ ПО Π’Π•ΠœΠ•