Сортиране по метод на пряко вмъкване - метод на картоиграча
Нека имаме предварително въведена редица от стойности - данни. Алгоритъмът за сортиране по метод на пряко вмъкване се среща в литературата и като метод на картоиграча. Това е добре познатият на картоиграчите метод за нареждане на картите, при който картоиграчът, държейки в лявата си ръка картите, ги изважда една по една и ги поставя на правилната им позиция. За вмъкване на картата на правилното място се налага последователното й сравнение с вече наредените карти, до откриване на правилната позиция.
Имаме масив от елементи от опреден тип, които искаме да сортираме. В основата на алгоритъма за сортиране чрез вмъкване стои достатъчно проста идея. Масивът се разделя на сортирана и несортирана област. Сортираната област обикновено се разполага в началото на масива, като първоначално обхваща само първия му елемент.Сортирането протича на n1 стъпки. На i-тата стъпка сортираната област се разширява с един елемент отдясно, като за целта добавяният i-ти елемент (нека го означим с x) се вмъква на подходящо място в сортираната последователност.
Как става вмъкването? Един очевиден алгоритъм е последователното сравнение и евентуална размяна на x със стоящия вляво от него елемент. Процесът продължава до възникване на една от следните ситуации:
а)достигане на елемент с ключ, по-малък или равен от този на x;
б)достигане на първия елемент на масива.
Двете проверки могат да се обединят в една чрез добавяне на елемент като нулев елемент на масива.
Това е добре познатият на картоиграчите метод за нареждане на картите, при който играчът, държейки в лявата си ръка картите, ги изважда една по една и ги поставя на правилната им позиция. За вмъкване на картата на правилното място се налага последователното й сравнение с вече наредените карти, до откриване на вярната позиция.
Имаме масив от елементи от опреден тип, които искаме да сортираме. В основата на алгоритъма за сортиране чрез вмъкване стои достатъчно проста идея. Масивът се разделя на сортирана и несортирана област. Сортираната област обикновено се разполага в началото на масива, като първоначално обхваща само първия му елемент.
Сортирането протича на n1 стъпки. На i-тата стъпка сортираната област се разширява с един елемент отдясно, като за целта добавяният i-ти елемент (нека го означим с x) се вмъква на подходящо място в сортираната последователност.
Как става вмъкването? Един очевиден алгоритъм е последователното сравнение и евентуална размяна на x със стоящия вляво от него елемент. Процесът продължава до възникване на една от следните ситуации:
а)достигане на елемент с ключ, по-малък или равен от този на x;
б)достигане на първия елемент на масива.
Двете проверки могат да се обединят в една чрез добавяне на елемент като нулев елемент на масива.
Следва решена задача с код на примерна програма (DEV C++), реализираща алгоритъм за сортиране по метода на пряко вмъкване - метод на картоиграча:
Блок схемата на алгоритъма е в приложените електронни уроци.
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.