Има няколко основни алгоритма за решаване на проблема със сортирането на масив. Един от най-известните сред тях е сортирането чрез вмъкване. Поради своята яснота и простота, но ниска ефективност, този метод се използва главно в обучението по програмиране. Позволява ви да разберете основните механизми за сортиране.
Описание на алгоритъма
Същността на алгоритъма за сортиране с вмъкване е, че в началния масив се формира правилно подреден сегмент. Всеки елемент се сравнява един по един с проверената част и се вкарва на правилното място. По този начин, след итерация през всички елементи, те се подреждат в правилния ред.
Редът на избор на елементи може да бъде произволен, те могат да бъдат избрани произволно или по някакъв алгоритъм. Най-често се използва последователно изброяване от началото на масива, където се формира подреден сегмент.
Началото на сортирането може да изглежда така:
- Вземете първия елемент от масива.
- Тъй като няма с какво да го сравните, вземете самия елемент, както е поръчанпоследователност.
- Отидете към втория елемент.
- Сравнете го с първия въз основа на правилото за сортиране.
- Ако е необходимо, разменете елементите на места.
- Вземете първите два елемента като подредена последователност.
- Отидете към третия елемент.
- Сравнете го с втория, разменете, ако е необходимо.
- Ако замяната е направена, сравнете я с първата.
- Вземете три елемента като подредена последователност.
И така нататък до края на оригиналния масив.
Сортиране на вмъкване в реалния живот
За по-голяма яснота си струва да дадете пример как този механизъм за сортиране се използва в ежедневието.
Вземете, например, портфейл. Сто, петстотин и хиляда долара банкноти лежат в безпорядък в отделението за банкноти. Това е бъркотия, в такава смес е трудно веднага да се намери подходящото парче хартия. Масивът от банкноти трябва да бъде сортиран.
Първата е банкнота от 1000 рубли, а веднага след нея - 100. Взимаме сто и я поставяме отпред. Третият по ред е 500 рубли, достойното място за него е между сто и хиляда.
По същия начин сортираме получените карти, когато играем на "Fool", за да улесним навигацията в тях.
Оператори и помощни функции
Методът за сортиране с вмъкване приема като вход първоначален масив за сортиране, функция за сравнение и, ако е необходимо, функция, която определя правилото за изброяване на елементи. Най-често се използва вместо товаредовен цикъл.
Първият елемент сам по себе си е подреден набор, така че сравнението започва от втория.
Алгоритъмът често използва помощна функция за обмен на две стойности (размяна). Той използва допълнителна временна променлива, която консумира памет и забавя малко кода.
Алтернатива е масово изместване на група елементи и след това вмъкване на текущия в свободното пространство. В този случай преходът към следващия елемент става, когато сравнението даде положителен резултат, което показва правилния ред.
Примери за внедряване
Конкретната реализация до голяма степен зависи от използвания език за програмиране, неговия синтаксис и структури.
Внедряване на класически C, използващо временна променлива за обмен на стойности:
int i, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; масив [j + 1]=масив [j]; масив [j]=темп; } }
PHP внедряване:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Тук първо всички елементи, които не отговарят на условието за сортиране, се изместват надясно и след това текущият елемент се вмъква в свободното пространство.
Java код, използващ while цикъл:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Общото значение на кода остава непроменено: всеки елемент от масива се сравнява последователно с предишните и се разменя с тях, ако е необходимо.
Прогнозно време за изпълнение
Очевидно, в най-добрия случай, входът на алгоритъма ще бъде масив, който вече е подреден по правилния начин. В тази ситуация алгоритъмът просто ще трябва да провери всеки елемент, за да се увери, че е на правилното място, без да прави обмени. По този начин времето за работа ще зависи пряко от дължината на оригиналния масив O(n).
Най-лошият вход е масив, сортиран в обратен ред. Това ще изисква голям брой пермутации, функцията по време на изпълнение ще зависи от броя на елементите на квадрат.
Точният брой пермутации за напълно неподреден масив може да се изчисли по формулата:
n(n-1)/2
където n е дължината на оригиналния масив. По този начин ще са необходими 4950 пермутации, за да се подредят 100 елемента в правилния ред.
Методът на вмъкване е много ефективен за сортиране на малки или частично сортирани масиви. Въпреки това, не се препоръчва да се прилага навсякъде поради високата сложност на изчисленията.
Алгоритъмът се използва като спомагателен в много други по-сложни методи за сортиране.
Сортиране на равни стойности
Алгоритъмът за вмъкване принадлежи към така наречените стабилни сортове. Това означава,че не разменя идентични елементи, а запазва оригиналния им ред. Индексът на стабилност в много случаи е важен за правилното подреждане.
По-горе е чудесен визуален пример за сортиране с вмъкване в танц.
