Суть алгоритма состоит в том, чтобы в исходном массиве найти наименьший элемент, а затем поменять местами первый элемент в списке с найденным. После того, находиться наименьший их оставшихся и меняется со вторым элементом. И так до тех пор, пока весь список не будет отсортирован.
Другими словами:
находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.
Т.о., идея сортировки с помощью выбора не сложнее двух предыдущих.
На j-ом этапе выбирается элемент наименьший среди M[j], M[j+1],. . ., M[N](см. процедуру FindMin) и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j], M[j+1],. . ., M[N]будут упорядочены.
Сказанное можно описать следующим образом:
Более точно:
begin for j:=1 to N-1 do begin FindMin(j, i); swap(M[j],M[i]) end end;
В программе, как уже было сказано, используется процедура FindMin, вычисляющая индекс lowindexэлемента, наименьшего среди элементов массива с индексами не меньше, чем startindex:
procedure FindMin(startindex: integer; var lowindex: integer); var lowelem: ...; u: integer; begin lowindex := startindex; lowelem := M[startindex]; for u:=startindex+1 to N do if M[u] < lowelem then begin lowelem := M[u]; lowindex := u end end;
Оценивая эффективность применения , учтите что в демонстрации сортировки выбором отсутствует пошаговое выполнение этой процедуры.
Итак:
Методы внутренней сортировки можно разбить в соответствии с определяющими их принципами на три класса:
Сортировка вставками: элементы просматриваются по одному, и каждый новый элемент вставляется на подходящую позицию среди ране упорядоченных элементов.
Сортировка с помощью выбора: сначала выделяется наименьший (или наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся элементов и т.д.
Сортировка с помощью обмена:последовательно просматриваются пары соседних элементов; если элементы в паре образуют инверсию (т.е. неупорядочены), то они меняются местами.
Все прямые методы сортировки фактически передвигают каждый элемент массива на каждом элементарном шаге на одну позицию. Поэтому требуют O(n2) таких шагов. В основу любых улучшенных методов положен принцип перемещения элементов на каждом шаге сортировки на большие расстояния. Такой подход позволяет существенно уменьшить время сортировки, но усложнить алгоритмы выполнения.
Улучшенный метод обмена – Шейкерная сортировка, метод Хоара (самый быстрый из известных на сегодняшний день методов внутренней сортировки), усовершенствование сортировки прямого включения – метод Шелла, прямого выбора – сортировка с помощью бинарного дерева.
Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные Up и Down содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка: Mid = (Up + Down)/2;
Если искомое значение меньше среднего элемента, мы переходим к поиску в левой половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Up становится (Mid – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
Подробнее:
− В начале переменная Up указывает на самый маленький - первый (левый) элемент массива (Up := 0), Down - на самый большой - последний (правый) (Down := n, где n - верхний индекс массива), а Mid - на средний.
Дальше,
− если искомое число равно Mid, то задача решена;
− если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;
− и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1.
− затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.
function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;
