Сортировка

Рассмотрим массив целых или вещественных чисел a₁, a₂, …, a_n. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по неубыванию a₁ £ a₂ £ … £ a_n или по невозрастанию a₁ ³ a₂ ³ … ³ a_n. Эта задача называется задачей сортировки или упорядочения массива. Для решения этой задачи можно воспользоваться, например, следующими алгоритмами:

а) Найти элемент массива, имеющий наименьшее (наибольшее) значение, переставить его с первым элементом. Затем проделать то же самое, начав со второго элемента и так далее. (Сортировка выбором)

б) Последовательным просмотром чисел a₁, a₂, …, a_n найти наименьшее i такое, что a_i > a_i+1 или a_i < a_i+1. Поменять a_i и a_i+1 местами, возобновить просмотр с элемента a_i+1 и так далее. Тем самым самое наибольшее или наименьшее число передвинется на последнее место. Следующие просмотры следует начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы. (Сортировка обменами)

в) Просматривать последовательно a₂, …, a_n и каждый новый элемент вставлять на подходящее место в уже упорядоченную последовательность a₁, …, a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами a₁, …, a_i-1. (Сортировка простыми вставками)

г) Сравнить элементы a₁ и a₂ и, если a₁ > a₂ (или a₁ < a₂), то эти элементы переставить. Далее сравнить элементы а₂ и а₃ и, если а₂ > a₃ (или а₂ < a₃), то их переставить. Далее сравнить элементы а₃ и а₄ и так далее до элементов a_n-1 и a_n включительно. Далее эти действия повторить, начиная опять с первого элемента. Последним является контрольный проход, при котором не будет перестановок элементов. (Сортировка по методу пузырька)