Идея сортировки Представим, что у нас есть неотсортированный массив A. Нам нужно его отсортировать по неубыванию. Давайте будем рассматривать поочерёдно каждый элемент массива, начиная со второго элемента(под индексом 1), и заканчивая последним элементом массива A. Процесс "рассмотрения" элемента будет выглядеть следующим образом: 1)Мы знаем, что слева от рассматриваемого нами элемента A[i] - элементы (A[j], где j < i и j >= 0) уже отсортированы, поэтому просто найдём в этой отсортированной части массива подходящеё место для вставки рассматриваемого нами элемента. 2)Вставим на это место рассматриваемый нами элемент. 3)Перейдём к рассмотрению следующего элемента. Время работы | Сложность В худшем случае - O(N^2) Реализация сортировки Код на c++: Код на c:
Идея сортировки
Представим, что у нас есть неотсортированный массив A. Нам нужно его отсортировать по неубыванию. Давайте будем рассматривать поочерёдно каждый элемент массива, начиная со второго элемента(под индексом 1), и заканчивая последним элементом массива A.
Процесс "рассмотрения" элемента будет выглядеть следующим образом:
1)Мы знаем, что слева от рассматриваемого нами элемента A[i] - элементы (A[j], где j < i и j >= 0) уже отсортированы, поэтому просто найдём в этой отсортированной части массива подходящеё место для вставки рассматриваемого нами элемента.
2)Вставим на это место рассматриваемый нами элемент.
3)Перейдём к рассмотрению следующего элемента.
Время работы | Сложность
В худшем случае - O(N^2)
Реализация сортировки
Код на c++:
Код на c: