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

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

#Случайный выбор элемента при неизвестном их количестве. (31306 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (33069 hits)
#Курсы валют. (61753 hits)
#Обработка шаблонных писем. (32190 hits)
#сортировка пузырьком. (144253 hits)
#Доступ ко всем полям и методам. (51821 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (52229 hits)
#Рисование множества Мандельброта. (38357 hits)
#Относительный путь к файлу. (34863 hits)
#Создание нестандартного (custom-ного) окна браузера. (31066 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (54785 hits)
#Рисование Фрактала (листьев папоротника). (47249 hits)
#Шейкер-сортировка. (63669 hits)
#Сравнение алгоритмов сортировки массива. (166519 hits)
#Арктангенс. (40716 hits)
#Наибольший общий делитель. (181189 hits)
#Вычисление двойного интеграла с использованием MPI. (53423 hits)
#Рисование окружности (по Брезенхэму). (28055 hits)
#Переключатель в кириллицу. (28195 hits)
#Синус. (54184 hits)


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

<< назад
распечататьобсудить >>


Сортировка вставкой
реализации: C++, количество: 3

Aвтор: this
Дата: 17.08.2002
Просмотров: 102391
Рейтинг: 3/7,4.94(4187)
реализации(исходники) +добавить

Коротко:

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

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

 псевдокод: сортировка вставкой, общий принцип  ссылка
  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[аноним:Ванюшка]


<< назад наверх
распечататьобсудить >>

каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.017518 секунд
Количество запросов к БД: 14, gzip: off