Алгоритм простого сортування вставками має у своїй основі просту ідею: перебрати усі елементи масиву і вставити їх у правильне місце. Так, як ви це робите, коли сортуєте свої карти в порядку зростання під час гри.
Припустимо, що масив, який необхідно відсортувати, має назву Array. Для того, щоб його відсортувати необхідні ще кілька змінних: x - змінна для збереження одного елементу масива, який ми потім вставимо в правильне місце, довжина масиву, яка зберігається в змінній під назвою N і ще дві змінні ітератори-бігунки - iter і jter. Тоді, в простому вигляді, наш цикл сортування (адже сортувати ми будемо в циклі - перебір усіх елементів) буде виглядати наступним чином:
for (iter=0; iter<N; iter++)
{
x = Array [iter] ;
/* вставити x у потрібне місце масиву Array */
}
А як нам обрати правильне місце вставки у масив? В цьому нам допоможе, дещо мидифікований, алгоритм лінійного пошуку. Отже для сортування елементів масиву у порядку зростання, нам необхідно знайти перший елемент, який менший за збережене значення масиву в змінній x, і якщо в даній позиції не виконується умова - посунути поточний елемент масиву вправо. Цикл виконується в зворотньому порядку (тобто від більшого індексу елемента до меншого) від позиції ітератора iter. Ось як тепер виглядає наш код сортування:
/* початок сортування */
/* Зверніть увагу, цикл починає з першого, а не нульового елементу! */
for (iter=1; iter<N; iter++) /* зовнішній цикл сортування */
{
x = Array [iter] ; /* зберігаємо значення елемента масиву */
/* знаходження правильного місця починається з місця iter */
jter = iter ;
/* вставляємо x у потрібне місце масиву Array */
while ( (jter>0) && (x<Array[jter-1]) ) /* внутрішній цикл */
{
/* якщо значення x менше за поточне в позиції (jter-1) -
** посуваємо елемент на позицію вліво (тобто ближче
** до початку масива) */
Array[jter] = Array[jter-1] ;
/* декремент ітератора бігунка (зменшення значення на одиницю) */
jter-- ;
}
/* ми знайшли необхідне місце у масиві -
** присвоїти йому наше збережене значення */
Array[jter] = x ;
}
Проста програма, яка використовує даний код, може виглядати наступним чином:
#include <iostream> /* для виводу на екран */
using namespace std; /* використовуємо простір імен з iostream */
int main (int argc, char** argv) /* головна функція програми */
{
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter, jter ; /* бігунки-ітератори для перебору масиву */
int x ; /* змінна, в якій тимччасово зберігається значення елементу масива*/
/* виводимо масив на екран (цей код можна вивести в процедуру) */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
/* початок сортування */
/* Зверніть увагу, цикл починає з першого, а не нульового елементу! */
for (iter=1; iter<N; iter++) /* зовнішній цикл сортування */
{
x = Array [iter] ; /* зберігаємо значення елемента масиву */
/* знаходження правильного місця починається з місця iter */
jter = iter ;
/* вставляємо x у потрібне місце масиву Array */
while ( (jter>0) && (x<Array[jter-1]) ) /* внутрішній зворотній цикл */
{
/* якщо значення x менше за поточне в позиції (jter-1) -
** посуваємо елемент на позицію вліво (тобто ближче
** до початку масива) */
Array[jter] = Array[jter-1] ;
/* декремент ітератора бігунка (зменшення значення на одиницю) */
jter-- ;
}
/* ми знайшли необхідне місце у масиві -
** присвоїти йому наше збережене значення */
Array[jter] = x ;
}
/* виводимо масив на екран */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ; /* вихід з програми */
}
Після виконання програми на комп'ютері, ми отримаємо наступне:
Усе, масив відсортовано в порядку зростання. Щоб отримати масив в порядку спадання, ми повинні модифікувати другий предикат умови внутрішнього циклу, заміною оператора '<' на оператор '>' (тобто просто заміняємо 'x<Array[jter-1]' на 'x>Array[jter-1]'):
#include <iostream> /* для виводу на екран */
using namespace std; /* використовуємо простір імен з iostream */
int main (int argc, char** argv) /* головна функція програми */
{
int Array [] = {11, 5, 7, 8, 3, 4, 2, 9, 0, 1, 6, 10, 13, 12} ;
int N = sizeof (Array) / sizeof (Array[0]) ; /* дізнаємося довжину масиву */
int iter, jter ; /* бігунки-ітератори для перебору масиву */
int x ; /* змінна, в якій тимччасово зберігається значення елементу масива*/
/* виводимо масив на екран */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
/* початок сортування */
/* Зверніть увагу, цикл починає з першого, а не нульового елементу! */
for (iter=1; iter<N; iter++) /* зовнішній цикл сортування */
{
x = Array [iter] ; /* зберігаємо значення елемента масиву */
/* знаходження правильного місця починається з місця iter */
jter = iter ;
/* вставляємо x у потрібне місце масиву Array */
/* модифіковано для порядку спадання */
while ( (jter>0) && (x>Array[jter-1]) ) /* внутрішній зворотній цикл */
{
/* якщо значення x більше за поточне в позиції (jter-1) -
** посуваємо елемент на позицію вліво (тобто ближче
** до початку масива) */
Array[jter] = Array[jter-1] ;
/* декремент ітератора бігунка (зменшення значення на одиницю) */
jter-- ;
}
/* ми знайшли необхідне місце у масиві -
** присвоїти йому наше збережене значення */
Array[jter] = x ;
}
/* виводимо масив на екран */
for (iter=0; iter<N; iter++)
{ cout << Array[iter] << " " ; }
cout << endl ;
return 0 ; /* вихід з програми */
}
Після виконання програми на комп'ютері ми отримаємо:
