Элементы массива условно разделяются на готовую последовательность ах,а2, ..., а{. и входную последовательность аи а2, ..., апЛ [1, 3, 9, 10, 13]. На каждом шаге z-й элемент помещается на подходящее место в готовую последовательность (рис. 3.2).
| Начальные ключи i = 1 i = 2 i = 3 i=4 i = 5 i = 6 i = 7 | |
| 44^12 42 94 18 06 67 | |
| ♦ | |
| 44| 14294 18 06 67 | |
| t | |
| 12|44 55^94 18 06 67 | |
| t | |
| 12|42|44 55g]18 06 67 | |
| T | |
| 12 42 44 55|94[Ц0667 | |
| ^^^F | |
| ^f | |
| 12|ia|4244 55 94ГЯ67 | |
| г---------------- "---------- ~ | |
| 0б|12 18 42 44 55 94 ГЯ | |
| ^^ | |
| 06 12 18 42 44 55|67|94 |
Рис. З.2. Пример сортировки Алгоритм сортировки
| for( i=l; i<n; | i++ ) |
| { | |
| x=a [ i ] ; | |
| включение х | на соответствующее место |
| среди a0, . . | • i Si |
| } |
В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т. е. х сравнивается с очередным элементом о,-, а затем либо х вставляется на свободное место, либо щ сдвигается (передаётся) вправо и процесс «уходит» влево. Процесс просеивания закончится при выполнении одного из двух следующих условий:
1. Найден элемент о,- с ключом, меньшим, чем ключ у х.
2. Достигнут левый конец готовой последовательности.