Как работает этот метод сортировки код?

Question

Это код сортировки одномерного массива на delphi.

Массив из 15 до этого случайно введенных элементов.

Помогите пожалуйста понять зачем тут два цикла.

Я понимаю этот код так: В цикле мы перебираем массив arr сравниваем текущий элемент с следующим и выполняем перестановку в зависимости от результата, но почему два цикла?

for i:= 1 to 15 do
    for j:= 1 to 14 do
      if arr[j] > arr[j+1] then
        begin
          x:= arr[j+1];
          arr[j+1]:= arr[j];
          arr[j]:= x;
        end;

Answer 1

Рассмотрим на примере:

Крайний случай для этого алгоритма - элементы отсортированы в обратном порядке, т.е.

arr = (15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

Уберем внешний цикл (по i), выполним внутренний (по j) 1 раз, и получим:

arr = (14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15)

т.е. максимальный элемент может смещаться вправо сразу на своё место, а вот минимальный влево - только на одну позицию.

Поэтому и нужно внешний цикл, т.к. минимальный влево нужно сдвинуть через весь массив.

Есть два замечания:

Внешний цикл (по i) достаточно выполнять N-1 (14) раз, так как именно столько действий нужно чтобы сместить элемент из одного края в другой.
Т.к. на каждой итерации i самых больших элементов оказываются на своих местах, то внутренний достаточно выполнять только для первых N-i элементов.

PS Для простой сортировки нужно сравнить каждый элемент с каждый, т.е. порядка N*N сравнений. Вложенные циклы как раз и дают такой порядок количества действий.

БЛОГ НА HUSL

Как работает этот метод сортировки код?

Ответы (1 шт):