Алгоритмы сортировки: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 34:
Пусть нам дан массив из ''N'' чисел. Заметим, что количество чисел, которые мы храним, по ходу работы алгоритма не изменяется: на каждом шаге мы просто переносим одно из чисел из исходного набора в результирующий. Поэтому нам нет надобности заводить новый массив для хранения результата: мы сможем хранить его в освободившихся ячейках старого массива.
 
После ''k''-го хода результат содержит ''k'' чисел, а исходный набор - ''N''-''k''. Договоримся, что текущий результат мы будем хранить в первых k элементах массива. Разберем подробнее, как это можно реализовать. Для этого вновь обратимся к нашему примеру:
3, 6, 1, 2, 9, 5.
На первом шаге мы находим наименьшее число - 1 - и должны переместить его на первое место. Но там уже записано число 3, куда же его деть? Ответ прост: на место числа 1. Таким образом, мы просто меняем местами два элемента массива:
'''1''' | 6, '''3''', 2, 9, 5.
Мы условно разделили массив на две части: в левой части хранится уже отсортированная часть - текущий результат, в правой - оставшиеся элементы исходного набора.
 
На втором шаге мы находим минмиальное число в правой части - среди элементов массива со 2-го по 6-й (в общем случае - по ''N''-й) - и меняем его местами с числом, стоящим на втором месте:
1, '''2''' | 3, 6, 9, 5.
Далее нам следует поставить следующее минимальное число - 3 - на третье место, но оно уже и так там стоит. Впрочем, мы не будем обращать на это внимание, и просто как бы поменяем его само с собой:
1, 2, '''3''' | 6, 9, 5.
Попробуем записать действия, которые нам предстоит проделать на шаге с номером ''k''. Сначала нам нужно найти наименьшее среди чисел, записанных в ''k'', ''k''+1, ..., ''N'' позициях массива. После этого нам нужно поменять этот элемент с ''k''-м.