Рассмотрим самые простые алгоритмы сортировки, используемые в обучении и тех случаях, когда асимптотикой при решении задачи можно пренебречь. Речь идет об алгоритмах сортировки "пузырьком" и "выбором". Далее, будем работать с некоторым массивом a[0..n-1], состоящим из n элементов сравнимого типа.

Сортировка выбором

Пожалуй, это самый легкий для реализации алгоритм среди существующих, идея которого сводится к последовательному позиционированию нужных элементов с 0-го по (n-1)-й. Вначале среди всех элементов определяется наименьший и меняется с 0-м, далее среди всех оставшихся снова находится наименьший и меняется со 1-м. Далее, среди элементов, начиная со 2-го так же находится наименьший и меняется с 2-м и т.д. до (n-2)-го элемента. Квадратичная сложность алгоритма очевидна, а алгоритм решения может выглядеть следующим образом:

Подробнее о сортировке выбором можно прочитать здесь.

Сортировка пузырьком

Это, наверное, самый популярный алгоритм сортировки, идея которого чем то похожа на предыдущий алгоритм: так же реализация сводится к позиционированию нужных элементов с 0-го по последний. Сама процедура установки текущего элемента в нужную позицию чем то напоминает всплытие пузырька. Для того, чтобы самый левый элемент (наименьший) встал на свое место необходимо справа налево пройтись по массиву, попарно сравнивая соседние элементы и в том случае, когда левый больше правого менять их местами. Для позиционирования следующего элемента, нужно пройтись еще раз по массиву, но не до 0-го а уже до 1-го элемента и т.д. Данный алгоритм, который как и предыдущий имеет квадратичную сложность, можно представить следующим образом:

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