Следующим алгоритмом, который мы рассмотрим, будет сортировка методом выбора (selection sort). Это пока что первый метод, который действительно можно использовать в повседневной практике (о пузырьковой сортировке и шейкер-сорти-ровке можно уже забыть).

Начиная с правого края колоды, просмотрите все карты и найдите самую младшую (конечно, это будет туз). Поменяйте местами туз с первой картой. Теперь, игнорируя первую карту, снова просмотрите всю колоду справа налево в поисках самой младшей карты. Поменяйте местами младшую карту со второй картой. Далее, игнорируя первые две карты, просмотрите всю колоду справа налево в поисках самой младшей карты и поменяйте найденную карту с третьей картой. Продолжайте процесс до тех пор, пока вся колода не будет отсортирована. Очевидно, что тринадцатый цикл не понадобится, поскольку он будет манипулировать только с одной картой, которая к тому времени уже будет находиться в требуемой позиции.

Листинг 5.6. Сортировка методом выбора

procedure TDSelectionSort (aList : TList;
aFirst : integer;
aLast : integer;
aCompare : TtdCompareFunc);
var
i, j : integer;
IndexOfMin : integer;
Temp : pointer;
begin
TDValidateListRange(aList, aFirst, aLast, 'TDSelectionSort1);
for i := aFirst to pred(aLast) do begin IndexOfMin : = i;
for j := succ(i) to aLast do if (aCompare(aList.ListA[j], aList.ListA[IndexOfMin]) <0) then
IndexOfMin : = j ; if (alndexOfMinoi) then begin Temp := aList.ListA[i];
aList.ListA[i] : = aList.ListA[IndexOfMin]; aList.ListA[IndexOfMin] : = Teilend;
end;
end;

Как видите, в приведенном коде снова присутствуют два вложенных цикла, следовательно, сортировка методом выбора относится к алгоритмам класса Oin2). В первом цикле индекс проходит значения от aFast до aLast-1 и при каждом его выполнении во внутреннем цикле определяется элемент с минимальным значением в оставшейся части списка. В отличие от нашего примера с картами, внутренний цикл заранее не знает, каковым будет минимальный элемент в списке, поэтому ему нужно просмотреть все элементы. После обнаружения минимального элемента он переставляется в требуемую позицию.

Сортировка методом выбора интересна одной своей особенностью. Количество выполняемых сравнений для первого прохода равно я, для второго - п-1 и т.д. Общее количество сравнений будет равно п (п + 1)/2~ 1, т.е. сортировка принадлежит к классу алгоритмов 0(п2). Тем не менее, количество перестановок намного меньше: при каждом выполнении внешнего цикла производится всего одна перестановка. Таким образом, общее количество перестановок (п - 1), т.е. 0(п). Что это означает на практике? Если стоимость перестановки элементов намного больше, чем время сравнения (под стоимостью в данном случае понимается время или требуемые ресурсы), сортировка методом выбора оказывается достаточно эффективной.

Сортировка методом выбора относится к группе устойчивых алгоритмов. Писк наименьшего значения будет возвращать первое в списке наименьшее значение из нескольких имеющихся. Таким образом, равные значения будут находиться в отсортированном списке в том же порядке, в котором они были в исходном списке.

Шейкер-сортировка || Оглавление || Сортировка методом вставок


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс