Сортировка массива методом пузырька

Как сказано в Википедии, алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N - 1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).

Проще говоря, Сортировка методом пузырька - это когда самое большое число (самый большой пузырёк) "всплывает" на самый верх, а за ним следуют все остальные:

bubble-sort-example-300px

С приведённой ниже задачей Вы уже встречались, когда решали задачи раздела "Цикл For и массивы. Решение тематических задач".

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

Пример:

Размер массива: 10
Массив:

10 8 5 4 6 7 9 3 1 2

Отсортированный массив:

1 2 3 4 5 6 7 8 9 10

Решение:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure main is
    type Matrix is array(Integer range <>) of Integer;
    n : Integer;
    imax : Integer;
    tmp : Integer;
begin
    Put("Размер массива: ");
    Get(n);
    declare
        mas : Matrix(1..n);
    begin
        --ввод массива
        Put_Line("Массив: ");
        for i in 1..mas'Last loop
            Get(mas(i));
        end loop;
 
        --сортировка массива
        for i in reverse 1..n loop   --внешний цикл - пробегаем с конца массива в начало
            imax := mas(i);          --индекс максимального элемента
            --внутренний цикл - пробегаем с начала массива до текущего i
            for j in 1..(i - 1) loop
            --(из внешнего цикла), не включая это i
                if mas(j) > mas(imax) then
                    --если на участке от 1 до i встретили элемент, который
                    --больше текущего максимального, то запоминаем его индекс
                    imax := j;
                end if;
            end loop;
            --найденный на участке массива максимальный элемент "всплывает" вверх
            tmp := mas(i);
            mas(i) := mas(imax);
            mas(imax) := tmp;
        end loop;
 
        --вывод массива
        Put_Line("Итоговый массив: ");
        for i in 1..mas'Last loop
            Put(Item => mas(i), Width => 1);
            Put(" ");
        end loop;
    end;
end main;

Добавить комментарий Отменить ответ