Сортировка данных в массиве

В этом разделе будет рассмотрен знаменитый алгоритм ''быстрой'' сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов – сортировку вставками.

Сортировка вставками

Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 1).

В функцию InsertionSort передается массив A и длина списка n. Рассмотрим i-ый проход (1<i<n-1). Подсписок от A[0] до A[i-1] уже отсортирован по возрастанию. В качестве вставляемого (TARGET) выберем элемент A[i] и будем продвигать его к началу списка, сравнивая с элементами A[i-1], A[i-2] и т.д. Просмотр заканчивается на элементе A[j], который меньше или равен TARGET, или находится в начале списка (j = 0). По мере продвижения к началу списка каждый элемент сдвигается вправо (A[j] = A[j-1]). Когда подходящее место для A[i] будет найдено, этот элемент вставляется в точку j.

Рис. 1