Съдържание[Крия][Покажи]
Компютърната наука е свързана с разбирането на сложността на алгоритмите и структурите от данни.
Имате списък с елементи, които трябва да бъдат сортирани, но нямате време или ресурси да използвате по-сложен алгоритъм за сортиране.
Сортирането чрез вмъкване е един от най-простите алгоритми за сортиране, но може да бъде бавен за големи списъци.
Лесното изпълнение и разбиране направиха този метод любим сред програмистите. Той е идеален за малки списъци или когато имате нужда от бързо решение.
В тази публикация в блога ще разгледаме времевата сложност на сортирането при вмъкване. Този алгоритъм се използва за сортиране на масиви и има време на изпълнение O(n2). Това означава, че времевата сложност се увеличава с размера на масива.
Този алгоритъм обаче често може да бъде по-бърз от други алгоритми за сортиране, като например бързо сортиране.
Нека да разгледаме по-отблизо как работи сортирането чрез вмъкване!
Какво представлява алгоритъмът за сортиране чрез вмъкване?
Елемент по елемент, сортирането чрез вмъкване генерира сортируем масив, който често се нарича списък.
Например, сортирането се прилага в сложни компютърни програми като компилатори, където редът на токените е важен за интерпретацията на програмата.
Как работи сортирането чрез вмъкване?
Когато използваме сортиране чрез вмъкване, за да сортираме масив, алгоритъмът започва с намиране на най-малкия елемент в списъка и вмъкването му на правилната позиция.
След това намира следващия най-малък елемент и го вмъква в правилната позиция и т.н.
Алгоритъмът работи, като преминава през списъка, сравнявайки всеки елемент с този, който идва преди него.
Ако елементите са в грешен ред, алгоритъмът ги разменя. След това проверява дали списъкът е сортиран и ако е, алгоритъмът приключва.
На практика сортирането чрез вмъкване често се реализира с помощта на няколко реда код, което го прави популярен избор за сортиране на малки масиви. При използването на този алгоритъм обаче трябва да се има предвид времевата сложност.
Пример:
Ето пример за това как работи сортирането чрез вмъкване. Ще използваме следния масив:
1, 2, 3, 4, 5, 6
Алгоритъмът започва с намиране на най-малкия елемент в списъка, който е 1. След това го вмъква на правилната позиция, първата позиция. След това намира следващия най-малък елемент, който е 2. Вмъква го в правилната позиция, която е втората позиция.
След това намира следващия най-малък елемент, който е 3. Вмъква го в правилната позиция, която е третата позиция.
След това намира следващия най-малък елемент, който е 4. Вмъква го в правилната позиция, която е четвъртата позиция и т.н. Списъкът вече е сортиран!
Можем да видим от примера, че алгоритъмът прави шест сравнения и суапове, за да сортира списъка. Това е така, защото отнема n2 сравнения и размени за сортиране на списък от n елемента. В този случай n=6.
Как да подобрим сложността на времето за сортиране на вмъкване?
Докато сортирането при вмъкване има време на изпълнение O(n2), може да се подобри чрез използване на по-добър алгоритъм за сортиране, като например бързо сортиране.
Quicksort има време за изпълнение O(n log n), което е много по-бързо от O(n2).
В някои случаи обаче сортирането чрез вмъкване може да бъде по-бързо от бързото сортиране.
Например, ако списъкът вече е подреден, сортирането чрез вмъкване ще отнеме по-малко време от бързото сортиране.
На практика сортирането чрез вмъкване често се реализира с помощта на няколко реда код, което го прави популярен избор за сортиране на малки масиви.
При използването на този алгоритъм обаче трябва да се има предвид времевата сложност.
Времеви сложности
Сложност в най-лошия случай O(n2):
Времевата сложност се увеличава с размера на масива. Това отнема n2 сравнения и размени за сортиране на списък от n елемента.
Например, ако имаме масив с размер 1000, алгоритъмът ще отнеме 1,000,000 XNUMX XNUMX сравнения и размени, за да сортира масива.
Най-добър случай Сложност O(n):
Времевата сложност е същата като размера на входния масив. аз
t взема n сравнения и размени, за да сортира списък от n елемента. Например, разгледайте масив с размер 5. Алгоритъмът ще отнеме пет сравнения и размени, за да сортира масива.
Средна сложност на случая O(n2):
Времевата сложност е между най-лошия и най-добрия случай на сложност в този случай.
Това отнема n2 сравнения и размени за сортиране на списък от n елемента.
По този начин сортирането чрез вмъкване е стабилен алгоритъм за сортиране.
Защо сортирането чрез вмъкване е стабилно?
Сортирането чрез вмъкване е стабилно, защото запазва реда на равните елементи във входния масив.
Това е важно за много приложения, като извличане на данни или финансов анализ. Например, ако имаме два списъка с числа и искаме да ги сравним, трябва да сме сигурни, че редът на елементите е запазен.
Ако списъците не са сортирани, няма да ги сравним точно.
Оставете коментар