CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Валидация, динамическая проверка заполнения html форм. (210468 hits)
#Как посчитать одинаковые пары за 1 проход (самая быстрая версия!). (2969 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (46663 hits)
#Вычисление значения полинома. (63100 hits)
#Постепенное затемнение. (52006 hits)
#Курсы валют. (68352 hits)
#"Липкие" окна. (32971 hits)
#Логирование в GUI. (33141 hits)
#Рисование куба. (60714 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (70591 hits)
#Интерактивная, динамическая подгрузка картинок. (70639 hits)
#Обновление нескольких записей таблицы. (33207 hits)
#Вычисление двойного интеграла с использованием MPI. (61076 hits)
#Плоттеры для рисования графиков. (30303 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (57619 hits)
#Постраничный вывод. (73774 hits)
#Рисование полусферы. (29749 hits)
#Поразрядная сортировка массива подсчетом. (134279 hits)
#Сапер. (54286 hits)
#Сохранение данных формы после перезагрузки через куки. (206632 hits)


Главная >> Каталог задач >> Сортировка >> Сортировка Вставками >> Сортировка вставкой

Сортировка вставкой

Aвтор:
Дата:
Просмотров: 113466
реализации(C++: 3шт...) +добавить

Коротко

Проходимся по всем элементам и вставляем каждый текущий элемент на свое место в уже отсортированную последовательность предыдущих просмотренных элементов. В самом начале считаем первый элемент уже отсортированной последовательностью и далее проходимся по всем остальным элементам.

В результате получим:

 псевдокод: сортировка вставкой, общий принцип  ссылка
  1. for i = 1 to n
  2. /* инвариант: элементы x[0..i-1] -
  3. уже отсортированы */
  4.  
  5. /* ставим x[i] в правильную позицию */
  6. insert x[i] in x[0..i-1]

Подробно

По книге Джона Бентли:
"Жемчужины программирования"

"...Большинство картежников, сами того не сознавая, пользуются именно таким методом сортировки для упорядочения пришедших им карт. Когда игрок получает очередную карту, все предыдущие уже отсортированы, поэтому он просто вставляет ее в нужное место. Для сортировки массива х[n] в порядке возрастания начинать следует с первого элемента, считая его отсортированной подпоследователь­ностью х[0..0]. Затем нужно вставлять элементы х[1], ..., х[n-1] в правильные позиции, как это делается в приведенном ниже псевдокоде:

 псевдокод: сортировка вставкой, общий принцип  ссылка
  1. for i = 1 to n
  2. /* инвариант: элементы x[0..i-1] -
  3. уже отсортированы */
  4.  
  5. /* ставим x[i] в правильную позицию */
  6. insert x[i] in x[0..i-1]


Последовательность сортировки массива из 4-х элементов иллюстрируется ниже. Символ "|" - показывает текущее значение переменной i; елементы слева от этого символа уже отсортированы, справа - нет.

3 | 1 4 2
1 3 | 4 2
1 3 4 | 2
1 2 3 4 |

Вставка элемента в нужную позицию производится циклом, в котором элементы перебираются справа налево, а в переменной j хранится индекс очередного вставляемого элемента. В цикле текущий элемент переставляется местами с предыдущим, если этот предыдущий элемент существует (то есть j>0) и текущий элемент еще не установлен в нужное положение (он и предыдущий элементы находятся в неправильном порядке). Итак, получившаяся программа сортировки примет вид:

 псевдокод: сортировка вставкой, версия #1  ссылка
  1. for i = 1 to n
  2. for (j = i; j > 0 && x[j-1] > x[j]; j--)
  3. swap(j-1, j);


В тех редких случаях, когда мне нужно написать свою собственную сортировку, я начинаю именно с этой функции, потому что она очень проста — всего три очевидные строки.

Программисты, стремящиеся к оптимизации, могут счесть нерациональным вызов функции swap из тела внутреннего цикла. Программу можно ускорить, раскрыв функцию явно, хотя многие оптимизирующие компиляторы способны делать это за нас. Заменим вызов функции нижеследующим кодом, в котором переменная t используется для обмена x[j] и x[j-l]:

t = x[j] x[j] = x[j-1] x[j-1] = t

На моем компьютере вторая версия сортировки работает примерно в три раза быстрее, чем первая.

После этого улучшения появляется возможность сделать следующий шаг. Поскольку переменной t несколько раз присваивается одно и то же значение (исходно находящееся в x[i]), мы можем вынести присваивания, относящиеся к этой переменной, за рамки внутреннего цикла, а также изменить вид сравнения, что даст третью версию сортировки вставкой:

 псевдокод: Сортировка вставкой, версия #3  ссылка
  1. for i = 1 to n
  2. t = x[i]
  3. for (j = i; j > 0 && x[j-1] > t; j--)
  4. x[j] = x[j-1]
  5. x[j] = t;


Эта программа сдвигает элементы вправо до тех пор, пока они превосходят значение t, а потом ставит t в правильную позицию. Эта функция из пяти строк чуть сложнее своих предшественников, но на моем компьютере она работает примерно на 15% быстрее, чем вторая версия той же сортировки.

Для случайного расположения элементов во входном массиве, как и в худшем случае (обратный порядок сортировки), время выполнения сортировки вставкой пропорционально O(n2). Таблица 11.1 содержит данные о времени выполнения трех программ, когда на вход подается n случайных целых чисел:

Третьей программе требуется несколько миллисекунд для сортировки n = 1000 целых чисел, треть секунды на n = 10 000 целых, и почти час на сортировку миллиона чисел. Скоро мы встретимся с программой, сортирующей миллион чисел меньше, чем за секунду. Если входной массив уже почти отсортирован, сортировка вставкой работает гораздо быстрее, поскольку все элементы сдвигаются лишь на небольшое расстояние. Алгоритм в разделе 11.3 данной главы(прим. ред-ра: т.е. алгоритм #2 задачи улучшение быстрой сортировки) основан именно на этом свойстве.
..."

Джон Бентли

Реализации:

C++(3)   +добавить

1) Сортировка вставкой, версия #3 на C++, code #17[автор:this]
2) Сортировка вставками на C++, code #604[аноним:bes]
3) работа fgets на C++, code #633[аноним:Ванюшка]