Змест[Схаваць][Паказаць]
Інфарматыка - гэта разуменне складанасці алгарытмаў і структур даных.
У вас ёсць спіс элементаў, якія неабходна адсартаваць, але ў вас няма часу або рэсурсаў, каб выкарыстоўваць больш складаны алгарытм сартавання.
Сартаванне ўстаўкай - адзін з самых простых алгарытмаў сартавання, але для вялікіх спісаў ён можа быць павольным.
Простая рэалізацыя і разуменне зрабілі гэты метад фаварытам сярод праграмістаў. Ён ідэальна падыходзіць для невялікіх спісаў або калі вам трэба хуткае рашэнне.
У гэтым паведамленні ў блогу мы разгледзім часовую складанасць сартавання ўстаўкі. Гэты алгарытм выкарыстоўваецца для сартавання масіваў і мае час выканання O(n2). Гэта азначае, што складанасць па часе ўзрастае з павелічэннем памеру масіва.
Аднак часта гэты алгарытм можа працаваць хутчэй, чым іншыя алгарытмы сартавання, такія як хуткая сартаванне.
Давайце больш падрабязна разгледзім, як працуе сартаванне ўстаўкай!
Што такое алгарытм сартавання ўстаўкай?
Па адным элеменце, сартаванне ўстаўкай стварае масіў, які можна сартаваць, які часта называюць спісам.
Напрыклад, сартаванне ўжываецца ў складаных камп'ютэрных праграмах, такіх як кампілятары, дзе парадак маркераў важны для інтэрпрэтацыі праграмы.
Як працуе сартаванне ўстаўкай?
Калі мы выкарыстоўваем сартаванне па ўстаўцы для сартавання масіва, алгарытм пачынаецца з пошуку найменшага элемента ў спісе і ўстаўкі яго ў правільную пазіцыю.
Затым ён знаходзіць наступны найменшы прадмет і ўстаўляе яго ў патрэбнае месца, і гэтак далей.
Алгарытм працуе, перабіраючы спіс, параўноўваючы кожны элемент з папярэднім.
Калі элементы размешчаны ў няправільным парадку, алгарытм мяняе іх месцамі. Затым ён правярае, ці адсартаваны спіс, і калі так, алгарытм завяршаецца.
На практыцы сартаванне ўстаўкай часта рэалізуецца з дапамогай некалькіх радкоў кода, што робіць яго папулярным выбарам для сартавання невялікіх масіваў. Аднак пры выкарыстанні гэтага алгарытму варта ўлічваць часовую складанасць.
прыклад:
Вось прыклад таго, як працуе сартаванне ўстаўкай. Мы будзем выкарыстоўваць наступны масіў:
1, 2, 3, 4, 5, 6
Алгарытм пачынаецца з пошуку найменшага элемента ў спісе, які роўны 1. Затым ён устаўляе яго ў правільную пазіцыю, першую пазіцыю. Затым ён знаходзіць наступны найменшы элемент, які роўны 2. Ён устаўляе яго ў правільную пазіцыю, якая з'яўляецца другой пазіцыяй.
Затым ён знаходзіць наступны найменшы элемент, які роўны 3. Ён устаўляе яго ў правільную пазіцыю, якая з'яўляецца трэцяй пазіцыяй.
Затым ён знаходзіць наступны найменшы элемент, які роўны 4. Ён устаўляе яго ў правільную пазіцыю, якая з'яўляецца чацвёртай пазіцыяй, і гэтак далей. Цяпер спіс адсартаваны!
З прыкладу мы бачым, што алгарытм выкарыстоўвае шэсць параўнанняў і месцаў для сартавання спісу. Гэта адбываецца таму, што гэта займае н2 параўнання і замены для сартавання спісу з n элементаў. У гэтым выпадку n=6.
Як павысіць складанасць часу сартавання ўстаўкі?
У той час як сартаванне ўстаўкай мае час выканання O(n2), яго можна палепшыць, выкарыстоўваючы лепшы алгарытм сартавання, напрыклад, хуткае сартаванне.
Quicksort мае час выканання O(n log n), які нашмат хутчэй, чым O(n2).
Аднак у некаторых выпадках сартаванне ўстаўкай можа быць хутчэй, чым хуткае сартаванне.
Напрыклад, калі спіс ужо ў парадку, сартаванне ўстаўкай зойме менш часу, чым хуткае сартаванне.
На практыцы сартаванне ўстаўкай часта рэалізуецца з дапамогай некалькіх радкоў кода, што робіць яго папулярным выбарам для сартавання невялікіх масіваў.
Аднак пры выкарыстанні гэтага алгарытму варта ўлічваць часовую складанасць.
Складанасці часу
Найгоршы варыянт складанасці O(n2):
Часовая складанасць павялічваецца з памерам масіва. Гэта займае н2 параўнання і замены для сартавання спісу з n элементаў.
Напрыклад, калі ў нас ёсць масіў памерам 1000, для сартавання масіва алгарытму спатрэбіцца 1,000,000 XNUMX XNUMX параўнанняў і замен.
Лепшы варыянт складанасці O(n):
Часовая складанасць такая ж, як і памер ўваходнага масіва. я
Для сартавання спісу з n элементаў патрабуецца n параўнанняў і месцаў. Напрыклад, разгледзім масіў памерам 5. Алгарытм будзе прымаць пяць параўнанняў і замен для сартавання масіва.
Сярэдняя складанасць выпадку O(n2):
Часовая складанасць у гэтым выпадку знаходзіцца паміж найгоршым і найлепшым складанасцю.
Гэта займае н2 параўнання і замены для сартавання спісу з n элементаў.
Такім чынам, сартаванне ўстаўкай з'яўляецца стабільным алгарытмам сартавання.
Чаму сартаванне ўстаўкай стабільнае?
Сартаванне ўстаўкай стабільнае, бо захоўвае парадак роўных элементаў ва ўваходным масіве.
Гэта важна для многіх прыкладанняў, такіх як пошук даных або фінансавы аналіз. Напрыклад, калі ў нас ёсць два спісы лікаў і мы хочам іх параўнаць, нам трэба пераканацца, што парадак элементаў захаваны.
Калі спісы не адсартаваныя, мы не будзем іх дакладна параўноўваць.
Пакінуць каментар