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