Ключова разлика – сортиране чрез вмъкване срещу сортиране при избор
Сортиране чрез вмъкване и сортиране по избор са два алгоритъма за сортиране, използвани за сортиране на колекция от данни. Понякога е необходимо данните да се подредят в определен ред. Алгоритмите за сортиране са механизми за сортиране на набор от данни. При сортирането данните се подреждат според цифров или лексикографски ред. Ако данните са сортирани правилно, тогава би било лесно да търсите данни по-бързо. Ако телефонните номера в телефонния указател не са сортирани, тогава ще бъде трудно да се намери конкретен телефонен номер. По същия начин, ако думите в речника не са подредени по азбучен ред, ще бъде много трудно да се намерят думи. Следователно сортирането е полезно в ежедневието. В компютърните науки има сортиращи алгоритми за сортиране на колекция от данни. Два такива алгоритъма са сортиране чрез вмъкване и сортиране при избор. Сортирането чрез вмъкване е алгоритъмът за сортиране, който сортира масива чрез изместване на елементи един по един. Сортирането при избор е алгоритъмът за сортиране, който намира най-малкия елемент в масива и разменя елемента с първата позиция, след това намира втория най-малък елемент и го разменя с елемента на втората позиция и продължава процеса, докато целият масив бъде сортиран. Основната разлика между сортирането чрез вмъкване и сортирането по избор е, че сортирането чрез вмъкване сравнява два елемента наведнъж, докато сортирането по избор избира минималния елемент от целия масив и го сортира.
Какво е сортиране чрез вмъкване?
Сортирането чрез вмъкване е алгоритъм за сортиране, базиран на сравнение на място. При този метод масивът се търси стъпка по стъпка. Несортираните елементи се преместват и вмъкват в сортирания подсписък на масива. Алгоритъмът за сортиране при вмъкване може да бъде обяснен със следния пример.
Например, вземете началния масив като 77, 33, 44, 11, 88. В този алгоритъм за сортиране първата стъпка е да изберете текущия елемент.
Текущият елемент е 77. Текущият елемент се сравнява с всички елементи в лявата страна. 77 е първият елемент и няма елементи от лявата страна. Индексът на текущата позиция е 0.
След това индексът на текущата позиция се увеличава с 1. Сега индексът е 1, а текущият елемент е 33. Когато го сравняваме с елемента вляво, той е по-малък от 77. След това и двете стойности се разменят. Сега 33 е в индекс 0, а 77 е в индекс1.
Сега масивът е 33, 77, 44, 11, 88.
Отново индексът се увеличава. Индексът е 2, а текущият елемент е 44. Сравнява се с елементите в лявата страна. 44 е по-малко от 77. Така че тези две стойности са разменени. Сега масивът е 33, 44, 77, 11, 88. Необходимо е да се сравнят всички елементи отляво. И така, 44 се сравнява с 33. 33 е по-малко от 44. Така че тези елементи не трябва да се обменят.
Сега масивът е 33, 44, 77, 11, 88.
Отново индексът се увеличава. Индексът е 3, а текущият елемент е 11. Сравнява се с всички елементи вляво. 11 е по-малко от 77, така че тези две са разменени. Сега масивът е 33, 44, 11, 77, 88. Когато сравняваме 11 и 44, 11 е по-малко от 44. Така че тези две се разменят. Сега масивите са 33, 11, 44, 77, 88. Отново 11 се сравнява с 33. 11 е по-малко от 33, така че тези две стойности се разменят.
Сега масивът е 11, 33, 44, 77, 88.
Увеличаването на индекса ще направи индекса 4. Стойността е 88. Тя е по-висока от 77. Така че няма нужда от размяна. И накрая, сортираният масив е 11, 33, 44, 77, 88.
Фигура 01: Пример за сортиране чрез вмъкване
Имплементацията на сортирането при вмъкване е както по-горе. Първоначалният масив беше 77, 33, 44, 11, 88. След сортиране той дава резултат 11, 33, 44, 77, 88.
Какво е сортиране при избор?
Сортирането при избор е алгоритъм за сортиране, базиран на сравнение на място. Масивите са разделени на секции. Сортираната част е в левия край. Несортираната част е в десния край. Първо трябва да се намери най-малката стойност. След това се разменя с левия елемент. Сега този елемент е в сортирания масив. Този процес продължава да премества границата на несортирания масив от един елемент надясно. Алгоритъмът за сортиране на селекцията може да бъде обяснен със следния пример.
Например, вземете началния масив като 77, 33, 44, 11, 88, 22. В този алгоритъм за сортиране се намира най-малкият в масива. Най-малкият елемент е 11. Той се разменя с елемента в индекса 0 на масива.
Сега масивът е 11, 33, 44, 77, 88, 22.
Най-малкият елемент е в индекса 0, така че 11 вече е сортиран. От останалите елементи най-малкият е 22. Той се разменя с индексния елемент 1st.
Сега масивът е 11, 22, 44, 77, 88, 33.
Елементите 11 и 22 вече са сортирани. От останалите, най-малката стойност е 33. Тя се заменя с 2nd индексен елемент.
Сега масивът е 11, 22, 33, 77, 88, 44.
Елементите 11, 22 и 33 вече са сортирани. От останалите, най-малката стойност е 44. Тя се заменя с индексния елемент 3rd.
Сега масивът е 11, 22, 33, 44, 88, 66.
Елементите 11, 22, 33, 44 вече са сортирани. Останалите елементи са 88 и 66. Елементът 66 е разменен с индексния елемент 4th.
Сега масивът е 11, 22, 33, 44, 66, 88.
Това е сортираният масив, използващ алгоритъм за сортиране по избор.
Фигура 02: Пример за сортиране при избор
Имплементацията на сортирането при вмъкване е както по-горе. Първоначалният масив беше 77, 33, 44, 11, 88. След сортиране той дава резултат 11, 33, 44, 77, 88.
Каква е приликата между сортиране чрез вмъкване и сортиране при избор?
Както сортирането чрез вмъкване, така и сортирането при избор са алгоритми за сортиране
Каква е разликата между сортиране чрез вмъкване и сортиране при избор?
Сортиране чрез вмъкване срещу сортиране при избор |
|
| Сортирането чрез вмъкване е алгоритъмът за сортиране, който сортира масива чрез изместване на елементи един по един. | Сортирането при избор е алгоритъмът за сортиране, който намира най-малкия елемент в масива и заменя елемента с първата позиция, след това намира втория най-малък елемент и го заменя с елемента на втората позиция и продължава процеса до целият масив е сортиран. |
| Процес | |
| Сортирането чрез вмъкване е да сортира подсписъка чрез сравняване на два елемента, докато целият масив бъде сортиран. | Сортирането при избор избира минималния елемент и го разменя с първата позиция, отново избира минимума за останалите и го разменя с втората позиция и продължава този процес до края. |
| Стабилност | |
| Сортирането чрез вмъкване е стабилен алгоритъм за сортиране. | Сортирането при избор не е стабилен алгоритъм за сортиране. |
Резюме – Сортиране при вмъкване срещу сортиране при избор
Понякога е необходимо да сортирате данните. В компютърните науки има алгоритми за сортиране на данни. Тази статия обсъжда двата алгоритъма за сортиране, които са сортиране чрез вмъкване и сортиране чрез избор. Сортирането чрез вмъкване е алгоритъмът за сортиране, който сортира масива чрез изместване на елементи един по един. Сортирането при избор е алгоритъмът за сортиране, който намира най-малкия елемент в масива и разменя елемента с първата позиция, след това намира втория най-малък елемент и го разменя с елемента на втората позиция и продължава процеса, докато целият масив бъде сортиран. Разликата между сортирането чрез вмъкване и сортирането по избор е, че сортирането чрез вмъкване сравнява два елемента едновременно, докато сортирането по избор избира минималния елемент от целия масив и го сортира.
Изтеглете PDF на сортиране чрез вмъкване срещу сортиране при избор
Можете да изтеглите PDF версията на тази статия и да я използвате за офлайн цели според бележката за цитиране. Моля, изтеглете PDF версията тук: Разлика между сортиране чрез вмъкване и сортиране при избор
