Большинство картежников, сами того не сознавая, пользуются именно таким методом сортировки для упорядочения пришедших им карт. Когда игрок получает очередную карту, все предыдущие уже отсортированы, поэтому он просто вставляет ее в нужное место. Для сортировки массива х[п] в порядке возрастания начинать следует с первого элемента, считая его отсортированной подпоследовательностью х[0..0]. Затем нужно вставлять элементы х[1], ..., х[п-1] в правильные позиции, как это делается в приведенном ниже псевдокоде:
for 1 = [ 1, п)
/* инвариант элементы х[0 i-l] отсортированы */
/* цель- вставить х[i ] в нужную позицию в массиве х[0 i] */
Последовательность сортировки массива из четырех элементов иллюстрируется ниже. Символ «|» показывает текущее значение переменной i; элементы слева от этого символа уже отсортированы, а справа — нет.
3 | 1 4 2
1 314 2
1 3 4 I 2
1 2 3 4|
Вставка элемента в нужную позицию производится циклом, в котором элементы перебираются справа налево, а в переменной j хранится индекс очередного вставляемого элемента. В цикле текущий элемент переставляется местами с предыдущим, если этот предыдущий элемент существует (то есть j>0) и текущий элемент еще не установлен в нужное положение (он и предыдущий элементы находятся в неправильном порядке). Итак, получившаяся программа сортировки вставкой приведена на листинге 11.1.
Листинг 11.1. Сортировка вставкой: версия 1
for 1 = [1. п)
for (j = 1. j > 0 && х[j-1] > х[j]. J - -) swap(j-1. j)
В тех редких случаях, когда мне нужно написать свою собственную сортировку, я начинаю именно с этой функции, потому что она очень проста — всего три очевидные строки.
Программисты, стремящиеся к оптимизации, могут счесть нерациональным вызов функции swap из тела внутреннего цикла. Программу можно ускорить, раскрыв функцию явно, хотя многие оптимизирующие компиляторы способны делать это за пас. Заменим вызов функции нижеследующим кодом, в котором переменная t используется для обмена x[j] и x[j-l].
t - Х[j ] . x[j] = х[j -1 ] ; x[j-l] = t
На моем компьютере вторая версия сортировки работает примерно в три раза быстрее, чем первая.
После этого улучшения появляется возможность сделать следующий шаг. Поскольку переменной t несколько раз присваивается одно и то же значение (исходно находящееся в x[i]), мы можем вынести присваивания, относящиеся к этой переменной, за рамки внутреннего цикла, а также изменить вид сравнения, что даст третью версию сортировки вставкой (листинг 11.2).
Опубликовал vovan666
April 17 2013 00:02:29 ·
0 Комментариев ·
3927 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
