Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. (pascal)

Метод пузырька — это классический алгоритм сортировки, который повторно проходит по списку, сравнивая соседние элементы и меняя их местами, если они идут в неправильном порядке. В обычной реализации внешний цикл продолжается до тех пор, пока не будет выполнено нужное количество проходов по списку. Однако можно оптимизировать метод пузырька, добавив условие, при котором алгоритм завершится досрочно, если на очередном шаге внешнего цикла не было перестановок. Это позволяет сократить количество проходов, если список уже отсортирован или почти отсортирован.

Вот пример такого метода пузырька на языке Pascal:

pascal
procedure BubbleSort(var arr: array of Integer);
var
  i, j, temp: Integer;
  swapped: Boolean;
begin
  // Проходим по всему массиву
  for i := 0 to High(arr) - 1 do
  begin
    swapped := False; // флаг, указывающий, были ли перестановки в ходе прохода
    // Проходим по массиву от 0 до High(arr) - i - 1
    for j := 0 to High(arr) - i - 1 do
    begin
      if arr[j] > arr[j + 1] then
      begin
        // Если элементы не в порядке, меняем их местами
        temp := arr[j];
        arr[j] := arr[j + 1];
        arr[j + 1] := temp;
        swapped := True; // Если переставили элементы, ставим флаг в True
      end;
    end;
    
    // Если не было перестановок, массив отсортирован и можно завершить сортировку
    if not swapped then
      Break;
  end;
end;

Объяснение работы алгоритма:

1. Внешний цикл (for i := 0 to High(arr) - 1) — этот цикл выполняется несколько раз, каждый раз с уменьшением диапазона, в котором выполняются перестановки, так как в конце массива элементы уже отсортированы.

2. Внутренний цикл (for j := 0 to High(arr) - i - 1) — в этом цикле происходит сравнение соседних элементов массива. Если элементы идут в неправильном порядке, они меняются местами.

3. Переменная swapped — флаг, который отслеживает, были ли в этом проходе перестановки. Если за проход не было сделано ни одной перестановки, это означает, что массив уже отсортирован, и можно завершить работу алгоритма досрочно.

4. Условие завершения — если после одного из проходов по массиву не было выполнено ни одной перестановки, то флаг swapped останется равным False, и программа завершит внешний цикл с помощью Break.

Преимущества:

• Алгоритм работает быстрее, если массив уже частично отсортирован или отсортирован полностью, поскольку он завершит работу раньше.
• Обычный метод пузырька всегда выполняет все проходы, даже если массив уже отсортирован, что делает его менее эффективным в таких случаях.