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

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

#Полезные утилиты, небольшие api и библиотеки и проч.. (64872 hits)
#Синус. (56680 hits)
#Косинус. (36011 hits)
#"Липкие" окна. (28106 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (136675 hits)
#Преобразование сумм из цифрового представления в строковое. (167257 hits)
#Переворот символов строки (или элементов одномерного массива). (107146 hits)
#Вращение 3D объекта. (32604 hits)
#Рисование линии. (35400 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (93226 hits)
#Использование компилируемых (prepared) запросов. (27293 hits)
#Рисование прямоугольника. (27820 hits)
#Случайный выбор элемента при неизвестном их количестве. (33134 hits)
#Таймер. (37603 hits)
#Сравнение алгоритмов сортировки массива. (171269 hits)
#Рисование полусферы. (24865 hits)
#Код. (171994 hits)
#Сохранение данных формы после перезагрузки через куки. (192119 hits)
#Найти максимальную сумму в последовательности. (124846 hits)
#Плоттеры для рисования графиков. (26718 hits)


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

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

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