Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Сортировка вставкою

Автор: kurzon 19.10.2007, 22:19

Сортировка " вставка " есть устойчива или нет?

Автор: esperant0 19.10.2007, 22:52

зависит

Автор: kurzon 20.10.2007, 09:36

Цитата(esperant0 @ 19.10.2007, 22:52)

зависит

Сортировка " вставка " есть устойчива или нет?

Автор: esperant0 20.10.2007, 12:21

Цитата(kurzon @ 20.10.2007, 09:36)

Цитата(esperant0 @ 19.10.2007, 22:52)

зависит

Сортировка " вставка " есть устойчива или нет?

зависит от реализации

Автор: 4d5a 21.10.2007, 19:25

Сортировка вставками устойчива. Ее реализация давным давно формализована (если говорить про классическую сортировку вставками)
В доказательство устойчивости->
Пусть в массиве встретились два одинаковых элемента a1 и a2. Алгоритм найдет вначале a1, поставит его в упорядоченную часть. Далее найдет a2, будет просеевать его через упорядоченную часть пока выполняется условие: (очередной a[j] из готовой части > a2), дойдет до элемента a1 и остановится, вставив a2 после a1.

Возможно немного сумбурно объяснил, спрашивайте если не пнятно, а вообщето на algolist.manual.ru все детально описано
Вставками сортировка (простая и со сторожевым элементом):
http://algolist.manual.ru/sort/insert_sort.php
Краткое описание:
http://algolist.manual.ru/sort/faq/q5.php

Код


template<class T>
void insertSort(T a[], long size) {
  T x;
  long i, j;

  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];

// поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];  // сдвигаем элемент направо, пока не дошли

// место найдено, вставить элемент
    a[j+1] = x;
  }
}