Заранее извиняюсь — возможно вопрос элементарный
-Не могу реализовать сортировку методом вставок
Суть:а1 становится 1-ым в б1, а2 срав. с б1,если а2<б1
б1 сдвиг вправо а1 занимает его место.
а3 срав. с б1 если меньше сдвиг а3 станов.б1 если больше
а3 срав. с б2 .выглядит так
А 10 4 11 9
Б 10
Б 4 10
Б 4 10 11
Б 4 9 10 11
Изучать C++ начал недавно, эти сортировки пробовал сделать
по разному-вроде все правильно,но не работает
Ну если кто сможет помочь -заранее спасибо.

Здравствуйте, Turd, Вы писали:

T>Заранее извиняюсь — возможно вопрос элементарный
T>-Не могу реализовать сортировку методом вставок

Посмотри здесь. А вообще мне больше нравится сортировка из stl

Здравствуйте, Jenyay, Вы писали:



J>Посмотри здесь. А вообще мне больше нравится сортировка из stl

Нет по-моему это пузырек

Здравствуйте, Turd, Вы писали:

T>Нет по-моему это пузырек

Да, действительно на пузырек смахивает. Правда там внизу в комментариях есть какой-то код, который написано что вставка, глянь может оно (щас разбираться нет времени).

Кстати, вот еще здесь

Здравствуйте, Jenyay, Вы писали:

T>>Нет по-моему это пузырек

J>Да, действительно на пузырек смахивает. Правда там внизу в комментариях есть какой-то код, который написано что вставка, глянь может оно (щас разбираться нет времени).

Есть несколько алгоритмов, похожих друг на друга.

(Внимание: следите за правым габаритом, ниже я использую как закрытые интервалы, так и полуинтервалы)

1) Вставки в общем виде
a[0..k) отсортирован, a[k..n) — ещё нет.
— ищем место j вставки a[k] в a[0..k) — причём поиск может быть двоичным либо линейным,
— переносим a[k] в позицию j, сдвигая массив a[j..k) вправо; — можно либо воспользоваться доп.памятью, либо выполнить k-j обменов
Затраты: O(n·log(n)) либо O(n^2) сравнений и O(n^2) копирований/обменов.

2) Обмены в общем виде
a[0..k) отсортирован и содержит k младших элементов всего массива, a[k..n) — остальные, неотсортированные
— ищем минимальный элемент m среди a[k..n) — естественно, линейный поиск
— выполняем обмен a[k],a[m] — либо обмен двух элементов, либо сдвиг массива a[k..m)
Затраты: O(n^2) сравнений (поиск минимумов), O(n) либо O(n^2) копирований/обменов.

Пузырёк — это техника реализации этих алгоритмов. Она состоит в том, что сравнение и обмен соседних элементов происходит сразу.
Получаются очень похожие, но тем не менее, разные алгоритмы:

1) Вставки пузырьком
Каждый раз пробулькиваем массив a[0..k] справа налево. Как только в позиции j обмена не происходит — останавливаемся (пузырёк с условием).
O(n^2) сравнений и O(n^2) обменов.

2) Обмены пузырьком
Пробулькиваем массив a[k..n) справа налево; не останавливаемся, если в какой-то позиции обмена не случилось (пузырёк без условия). На пузырёк налипает минимум этого подмассива, который выносится в позицию a[k].
O(n^2) сравнений и O(n^2) обменов.
Этот алгоритм неэффективен — выполняются m-k обменов соседей вместо одного обмена несмежных элементов k,m.
Однако он имеет резерв для оптимизации: если на участке [k..l) не было обменов, это значит, что a[k..l) уже содержит упорядоченно l-k минимумов, и следующую итерацию можно начинать не с k+1, а с l.

3) Пинг-понг
a[0..k) и a[m..n) содержат упорядоченно k минимумов и n-m максимумов.
Гоняем пузырёк без условия по [k..m) то слева направо, то справа налево. Каждый раз к нему налипает то очередной максимум, то очередной минимум.
Плюс помним об оптимизации.

P.S.
Если не наглядно объяснил — могу картинки нарисовать.

Здравствуйте, Jenyay, Вы писали:

J>Кстати, вот еще здесь
Ладно, спасибо за помошь
Сегодня сдавал эти сортировки
1)методом выбора
2)метод вставки(тот который здесь решил отнести)
Так выяснилось что вместо 1-го я сделал метод пузырька, а тот который по ссылке оказался модифицированным вариантом 1-го