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

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

#Случайный выбор элемента при неизвестном их количестве. (31639 hits)
#Простая быстрая сортировка. (104456 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (51623 hits)
#Сортировка Шелла, оптимальный выбор приращений. (181825 hits)
#Вставка новой записи в таблицу БД. (31136 hits)
#Таймер. (35836 hits)
#Рисование полусферы. (23118 hits)
#Рисование линии. (33486 hits)
#Подмножество с максимальной суммой. (120040 hits)
#Подсветка синтаксиса. (27212 hits)
#Постраничный вывод. (64671 hits)
#Работа с камерой. (30631 hits)
#Двусторонняя карта. (28443 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (130439 hits)
#Сортировка Шелла, обший принцип. (136818 hits)
#Создание простейшей таблицы. (31777 hits)
#Постепенное затемнение. (45259 hits)
#Вращение 3D объекта. (31193 hits)
#Код. (168967 hits)
#Косинус. (34440 hits)


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



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

Aвтор:
Дата:
Просмотров: 102852
реализации(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, code #17[автор:this]
2) Сортировка вставками, code #604[аноним:bes]
3) работа fgets, code #633[аноним:Ванюшка]



© 2006-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.016325 секунд
Количество запросов к БД: 14, gzip: off