Алгоритм Сортировка вставками.

Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10, 100, 1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10, 50, 100, 500, 1000 - Вот вам
и алгоритм " Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.

//Сортировка вставками {---

Функция СортировкаВставками(Знач Массив)

Для i = 0 По Массив.ВГраница()-1 Цикл

Ключ = i + 1;

Замена = Массив[Ключ];

j = i + 1;

Пока j > 0 И Замена < Массив[j - 1] Цикл

Массив[j] = Массив[j - 1];

Замена = j - 1;

Ключ = j - 1;

j = j - 1;

КонецЦикла;

Массив[Ключ] = Замена;

КонецЦикла;

Возврат Массив;

КонецФункции

//---}

Алгортим " Сортировка слиянием".

Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируяпоэлементно значения подмассивов.

p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.

//Сортировка слиянием {---

Функция СортировкаСлиянием(Знач Массив)

Если Массив.Количество() = 1 Тогда

Возврат Массив;

КонецЕсли;

ТочкаРазрыв = Массив.Количество() / 2;

лМассив = Новый Массив;

прМассив = Новый Массив;

Для Сч = 0 ПО Массив.ВГраница() Цикл

Если Сч < ТочкаРазрыв Тогда

лМассив.Добавить(Массив[Сч]);

Иначе

прМассив.Добавить(Массив[Сч]);

КонецЕсли;

КонецЦикла;

Возврат Слияние(СортировкаСлиянием(лМассив), СортировкаСлиянием(прМассив));

КонецФункции

Функция Слияние(массив1, массив2)

a = 0;

b = 0;

слМассив = Новый Массив;

Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл

слМассив.Добавить();

КонецЦикла;

Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл

Если b < массив2.Количество() И a < массив1.Количество() Тогда

Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда

слМассив[i] = массив2[b];

b = b + 1;

Иначе

слМассив[i] = массив1[a];

a = a + 1;

КонецЕсли;

Иначе

Если b < массив2.количество() Тогда

слМассив[i] = массив2[b];

b = b + 1;

Иначе

слМассив[i] = массив1[a];

a = a + 1;

КонецЕсли;

КонецЕсли;

КонецЦикла;

Возврат слМассив;

КонецФункции

//---}