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

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

#Вычисление минимального / максимального значения. (70726 hits)
#Преобразование целых чисел в битовый массив. (34204 hits)
#Шейкер-сортировка. (66651 hits)
#Создание нестандартного (custom-ного) окна браузера. (33152 hits)
#Код. (172545 hits)
#Найти максимальную сумму в последовательности. (125706 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (53484 hits)
#Постраничный вывод. (67368 hits)
#ООП на javascript: классы, наследование, инкапсуляция. (251581 hits)
#Заливка замкнутой области. (59039 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (93771 hits)
#Вычисление медианы заданной выборки. (46414 hits)
#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (42955 hits)
#Сортировка Шелла, обший принцип. (139531 hits)
#Преобразование сумм из цифрового представления в строковое. (167820 hits)
#Бинарный поиск в массиве и его разновидности. (159296 hits)
#Переключатель в кириллицу. (30095 hits)
#Древовидные структуры. (53868 hits)
#Пирамидальная сортировка. (193528 hits)
#Поразрядная сортировка, общий принцип. (123302 hits)


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

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

Aвтор:
Дата:
Просмотров: 107063
реализации(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[аноним:Ванюшка]