Сортирането е основна операция, при която елементите на масив са подредени в някакъв специфичен ред, за да се подобри неговата възможност за търсене. С прости думи, данните се сортират така, че да могат лесно да се търсят.
Сравнителна таблица
| Основа за сравнение | Сортиране на вмъкване | Сортиране на селекцията |
|---|---|---|
| Основен | Данните се сортират чрез вмъкване на данните в съществуващ сортиран файл. | Данните се сортират чрез избиране и поставяне на последователните елементи в сортирано място. |
| природа | стабилен | нестабилен |
| Процес, който трябва да се следва | Елементите са известни предварително, докато се търси мястото за поставянето им. | Местоположението е известно преди, докато се търсят елементи. |
| Незабавни данни | Insertion sort е техника за сортиране на живо, която може да се справи с незабавни данни. | Тя не може да се справи с непосредствените данни, тя трябва да присъства в началото. |
| Най-добра сложност на случая | О (п) | O (n 2 ) |
Определение за сортиране на вмъкване
Сортирането на вмъкване работи чрез вмъкване на набор от стойности в съществуващия сортиран файл. Той изгражда сортирания масив, като вмъква по един елемент в даден момент. Този процес продължава, докато целият масив се сортира по някакъв ред. Основната концепция зад сортирането е да се вмъкне всеки елемент в съответното му място в окончателния списък. Методът за сортиране на вмъкване спестява ефективно количество памет.
Работа на сортировката Insertion
- Той използва два набора от масиви, където се съхраняват сортираните данни и други на несортирани данни.
- Алгоритъмът за сортиране работи, докато има елементи в несортирания набор.
- Да приемем, че има 'n' брой елементи в масива. Първоначално елементът с индекс 0 (LB = 0) съществува в сортирания набор. Оставащите елементи са в несортиран дял от списъка.
- Първият елемент на несортираната част има индекс на масив 1 (Ако LB = 0).
- След всяка итерация той избира първия елемент на несортирания дял и го вмъква в правилното място в сортирания набор.
Предимства на сортирането на вмъкване
- Лесно се изпълнява и много ефективно, когато се използва с малки набори от данни.
- Допълнителното изискване за място за вмъкване е по-малко (т.е. O (1)).
- Смята се, че е техника за сортиране на живо, тъй като списъкът може да бъде сортиран по начина на получаване на новите елементи.
- Той е по-бърз от други алгоритми за сортиране.
Пример:
Определение на сортирането на селекцията
Сортирането по селекция извършва сортиране чрез търсене на минималния номер на стойността и поставянето му в първата или последната позиция според реда (възходящ или низходящ). Процесът на търсене на минималния ключ и поставянето му в правилната позиция се продължава, докато всички елементи бъдат поставени в правилната позиция.
Работа на сортирането на селекцията
- Да предположим масив ARR с N елемента в паметта.
- При първото преминаване най-малкият ключ се търси заедно с неговата позиция, след което ARR [POS] се сменя с ARR [0]. Следователно ARR [0] се сортира.
- При второто преминаване отново се определя позицията на най-малката стойност в подмасива на N-1 елементите. Обменете ARR [POS] с ARR [1].
- В прохода N-1 се извършва същият процес за сортиране на N броя елементи.
Пример:
Ключови разлики между сортирането и сортирането на вмъкване
- Сортирането на вмъкване обикновено извършва операцията по вмъкване. Напротив, селекционният вид извършва подбора и позиционирането на необходимите елементи.
- Сортът за вмъкване се казва, че е стабилен, докато сортирането на селекцията не е стабилен алгоритъм.
- В алгоритъма за сортиране на вмъкнатите елементи са известни преди това. За разлика от това, сортирането за подбор съдържа предварително местоположението.
- Insertion sort е техника за сортиране на живо, където пристигащите елементи се сортират веднага в списъка, докато сортирането на селекцията не може да работи добре с незабавни данни.
- Сортът за вмъкване има времето за изпълнение O (n) в най-добрия случай. В противовес на това, най-добрата сложност на време за изпълнение на подбора е O (n2).
Сложността на сортирането на вмъкването
Най-добрата сложност на вмъкването е O (n) пъти, т.е. когато масивът е предварително сортиран. По същия начин, когато масивът се сортира в обратен ред, първият елемент на несортирания масив се сравнява с всеки елемент в сортирания набор. Така че в най-лошия случай времето за изпълнение на сортирането на вмъкване е квадратично, т.е. O (n2) . В средния случай също трябва да направи минимални (k-1) / 2 сравнения. Следователно средният случай също има квадратично време на работа O (n2).
Сложността на сортирането на селекцията
Тъй като работата на селекцията, сортирането не зависи от първоначалния ред на елементите в масива, така че няма голяма разлика между най-добрия случай и най-лошия случай на подбор.
Сортирането на селекцията избира елемента за минимална стойност, в процеса на селекция се сканира целия брой n-елементите; следователно n-1 сравнения са направени при първото преминаване. След това елементите се разменят. По същия начин във втория проход, за да намерим втория най-малък елемент, изискваме сканиране на останалите n-1 елементи и процесът продължава до сортиране на целия масив.
По този начин, сложността на време за изпълнение на сортирането на селекцията е O (n2) .
= (п-1) + (п-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
заключение
Сред двата алгоритъма за сортиране сортировката на вмъкване е бърза, ефективна, стабилна, докато сортирането на селекцията работи ефективно само когато е включен малък набор от елементи или списъкът е частично подреден. Броят на сравненията, направени чрез сортиране на селекцията, е по-голям от извършените движения, докато при вмъкване на сортиране броят пъти, когато даден елемент е преместен или подменен е по-голям от направените сравнения.
