Алгоритим быстрой сортировки массива

Delphi , Синтаксис , Сортировка

Автор: Dimka Maslov
WEB-сайт: http://delphibase.endimus.com

{ **** UBPFD *********** by delphibase.endimus.com ****
>> Алгоритим быстрой сортировки массива

Функция, показывающая пример реализации алгоритма быстрой сортировки
целочисленного массива. Легко может быть переработан для массивов
другого типа или объектов типа TList, TStringList и т. д.

Используемые параметры
IntArray - указатель на первый элемент массива. ВАЖНО! Индекс первого элемента
массива обязательно должен быть нулевым.

Low - минимальный индекс элемента массива
High - максимальный индекс элемента массива

Зависимости: нет
Автор:       Dimka Maslov, mainbox@endimus.ru, ICQ:148442121, Санкт-Петербург
Copyright:   http://www.rsdn.ru/article/?alg/bintree/sort.xml
Дата:        21 мая 2002 г.
***************************************************** }

type
  PIntArray = ^TIntArray;
  TIntArray = array[0..0] of Integer;

procedure QuickSort(IntArray: PIntArray; Low, High: Integer);

  procedure Swap(Index1, Index2: Integer);
  var
    N: Integer;
  begin
    N := IntArray[Index1];
    IntArray[Index1] := IntArray[Index2];
    IntArray[Index2] := N;
  end;

var
  Mid: Integer;
  Item: Integer;
  ScanUp, ScanDown: Integer;
begin
  // Здесь реализована сортировка по убыванию
  // Для реализации по возрастанию замените операции
  // сравнения на приведённые в комментариях
  if High - Low <= 0 then
    exit;
  if High - Low = 1 then
  begin
    if IntArray[High] {<} > IntArray[Low] then
      Swap(Low, High);
    Exit;
  end;
  Mid := (High + Low) shr 1;
  Item := IntArray[Mid];
  Swap(Mid, Low);
  ScanUp := Low + 1;
  ScanDown := High;
  repeat
    while (ScanUp <= ScanDown) and (IntArray[ScanUp] {<=} >= Item) do
      Inc(ScanUp);
    while (IntArray[ScanDown] {>} < Item) do
      Dec(ScanDown);
    if (ScanUp < ScanDown) then
      Swap(ScanUp, ScanDown);
  until (ScanUp >= ScanDown);
  IntArray[Low] := IntArray[ScanDown];
  IntArray[ScanDown] := Item;
  if (Low < ScanDown - 1) then
    QuickSort(IntArray, Low, ScanDown - 1);
  if (ScanDown + 1 < High) then
    QuickSort(IntArray, ScanDown + 1, High);
end;

Пример использования:

procedure TForm1.Button1Click(Sender: TObject);
var
  A: array[0..10] of Integer;
  i: Integer;
begin
  Randomize;
  for i := 0 to 10 do
    A[i] := Random(1000);
  QuickSort(@A, 0, 10);
  for i := 0 to 10 do
    Memo1.Lines.Add(IntToStr(A[i]));
end;

Код, который вы опубликовали, - это реализация алгоритма QuickSort в языке программирования Delphi, разработанном Borland. Вот подробное описание того, что код делает и как он работает:

Алгоритм

QuickSort - это алгоритм разделения и рекурсивного конкура, который сортирует массив целых чисел, рекурсивно делив массив на два подмассива: один с элементами, меньшими или равными pivot-элементу, и другой с элементами, большие pivot-элемент. Процесс повторяется, пока каждый подмассив не содержит только один элемент.

Код

Код состоит из следующих компонентов:

1. Декларации типов: Декларируются типы PIntArray и TIntArray как указатели и массивы соответственно.
2. Процедура QuickSort: Основная процедура сортировки, которая принимает три параметра: указатель на целочисленный массив (IntArray), нижний индекс (Low) и верхний индекс (High). Она сортирует массив в порядке убывания (т.е., самые большие элементы сначала).
3. Процедура Swap: Утилитарная процедура, которая обменивает два элемента в массиве.
4. Основной логик: Процедура QuickSort повторяет следующие шаги:
   • Если длина подмассива равна 0 или 1, она возвращает сразу (поскольку он уже отсортирован).
   • Если длина подмассива равна 2, она сравнивает два элемента и обменивает их, если необходимо.
   • Она рассчитывает середину (Mid) подмассива, устанавливает pivot-элемент в IntArray[Mid] и обменивает его с первым элементом (Low).
   • Она initializes two индексов: ScanUp (начиная от Low + 1) и ScanDown (начиная от High). Эти индексы будут использоваться для разделения подмассива.
   • Алгоритм повторно перемещает элементы в ScanUp и ScanDown, пока они не встретятся. Элементы, меньшие или равные pivot-элементу, перемещаются влево от pivot, а элементы, большие pivot-элемента, - вправо.
   • Когда разделение будет завершено, она устанавливает IntArray[Low] в pivot-элемент и рекурсивно вызывает QuickSort для двух подмассивов.

Пример использования

Код предоставляет пример использования в форме (TForm1), где событийный обработчик кнопки генерирует случайный массив из 11 целых чисел (от 0 до 1000), сортирует его с помощью процедуры QuickSort и отображает отсортированный массив в компоненте мемо (Memo1).

Замечания

• Алгоритм реализован для сортировки в порядке убывания. Для сортировки в порядке возрастания просто измените операторы сравнения в внутреннем цикле процедуры QuickSort.
• Это реализация предполагает, что входной массив не пуст и имеет хотя бы два элемента.

В целом, этот код предоставляет хороший пример реализации алгоритма QuickSort в Delphi и демонстрирует его эффективность для сортировки массивов целых чисел.

Алгоритм быстрой сортировки массива на языке Delphi, демонстрирующий пример реализации для целочисленного массива с помощью процедуры QuickSort.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Сортировка ::