“Карты, деньги, два ствола”
Самая наивная реализация, на вход получаем последовательность n чисел, на выходе - массив этих отсортированных чисел.
Эффективен на небольшом количестве элементов. Почему наверху картинка карт - так, не задумываясь, сортируем колоду карт: пусть вначале на руках нет ни одной карты и все лежат рубашкой вниз. Берётся по одной карте, каждая из которых помещается в нужное место, сравнивая ее масть и циферку с теми, что уже на руках
Псевдокодик на псевдоплюсах (не пугаться):
insertion-sort(A) { // получаем массив неотсорт. значений
for i = 2 to A.length { // проходимся по массиву
key = A[i] // сохраняем в переменную значение текущего элемента
j = i - 1 // до i - 1 всё (пока что) отсортировано по возрастанию
while (j > 0) and (A[j] > key) { // если элемент слева больше чем тот,
// который мы проверяем - нужно свопнуть
A[j + 1] = A[j] // собсна "двигаем" все элементы для впихуя key
j-- // чтобы пройтись по всем элементам слева
}
A[j + 1] = key // вставляем на нужное место (тут j уже м.б. не i - 1)
}
}
Че по асимптотике?
Реализация выше не требует никакой доп. памяти, т.к. действия происходят в самом массиве. Но есть реализации, где нужен ещё один доп. массив, тогда память будет занимать O(n).
По времени всё довольно просто - здесь вложенный цикл, ⇒ алгоритм пройдётся для каждого элемента (n штук) по n раз, асимптотика по времени будет O(n²)