Для решения многих задач необходимо упорядочить исходные данные по определенному признаку. Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений, произведенных в процессе выполнения алгоритма.
Сортировки методом простого выбора. Находят максимальный элемент в массиве из N элементов и меняют его местами с последним элементом (сортировка по возрастанию). Далее рассматривают массив без последнего элемента N-1. Общее количество сравнений пропорционально N2.
Сортировка методом поплавка. Рассматривается весь массив и максимальный элемент постепенно перемещается на последнее место. Затем рассматривают массив из N-1 элементов. Общее количество сравнений пропорционально N2.
Сортировка методом вставок. На i-м шаге считается, что первая часть массива, содержащая i-1 элемент, уже упорядочена. Далее берется i-й элемент, и для него подбирается j-е место в отсортированной части массива, такое, что упорядоченность не нарушается. i-й элемент помещается на это место, таким образом, что отсортированная часть массива увеличивается на один элемент. Общее количество сравнений пропорционально N2.