VPF::Сортировка вставкою - Форум программистов

kurzon

Дата 19.10.2007, 22:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: нет
Всего: -11

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

esperant0

Дата 19.10.2007, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

зависит

--------------------

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

kurzon

Дата 20.10.2007, 09:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 307
Регистрация: 12.8.2007

Репутация: нет
Всего: -11

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

зависит

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

esperant0

Дата 20.10.2007, 12:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

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

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

зависит

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

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

--------------------

4d5a

Дата 21.10.2007, 19:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.6.2007

Репутация: 1
Всего: 1

Сортировка вставками устойчива. Ее реализация давным давно формализована (если говорить про классическую сортировку вставками)
В доказательство устойчивости->
Пусть в массиве встретились два одинаковых элемента 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;
  }
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »