Здравствуйте, 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.
Если не наглядно объяснил — могу картинки нарисовать.