Требуется отсортировать массив по неубыванию методом пузырька

Требуется отсортировать массив по неубыванию методом пузырька

Задача

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

Решение

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Входные данные
В первой строке вводится одно натуральное число, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

  • Попроси больше объяснений
  • Следить
  • Отметить нарушение

Георгиус 24.02.2016

Что ты хочешь узнать?

Ответ

Как ч понял сортировка по неубыванию это сортировка по возрастанию. То есть легкие элементы всплывают наверх, а тяжелые перемещаются вниз:

//Pascal
const m = 1000
var
arr: array[1..m] of integer;
n,i, j, k: integer;
begin
readln(n);
write (‘Исходный массив: ‘);
for i := 1 to n do begin
readln(arr[i]);
end;
//сортировка методом пузырька
for i := 1 to n-1 do
for j := 1 to n-i do
if arr[j] > arr[j+1] then begin
k := arr[j];
arr[j] := arr[j+1];
arr[j+1] := k
end;

Читайте также:  Как зайти в папку стим

write (‘Отсортированный массив: ‘);
for i := 1 to n do
write (arr[i]:4);
end.

Алгоритм сортировки на классическом языке программирования С

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

Можете просмотреть следующее видео — изображающее принцип работы некоторых алгоритмов сортировки:

Один из самый простых алгоритмов сортировки, изучаемый в школьном курсе информатики — «Сортировка методом Пузырька». Его нельзя назвать быстрым, но он очень прост в понимании и реализации. Подходит для сортировки небольших списков (массивов).

Работу данного алгоритма представил в виде танца коллектив из Финляндии

Как видно из видео процесс сортировки заключается в следующем:

  1. Сравнивается i-ый элемент списка с i+1 — ым. Если больший из них имеет меньший порядковый номер, то они меняются местами (для сортировки по возрастанию)
  2. Таким образом, самый большой элемент сдвигается в конец списка
  3. Далее процесс повторяется, но не до конца списка, а до последнего отсортированного элемента

Например:

Дан список (массив): 0, 5, 8, 4, 9, 3

Расположим элементы списка в процессе убывания. Т.е. если элемент меньше своего соседа справа — меняется с ним местами.

После первого прохождения по списку первый нолик становится на последнее место

Как можно заметить количество сравнений уменьшилось на единицу, так как число 0 — минимальное заняло свое законное место при первой итерации и сравнивать с ним нет смысла.

В итоге получаем отсортированный список:

Для списка из шести элементов достаточно выполнить пять «проходов» по списку, поочередно сравнивая соседние элементы.

Читайте также:  Робот который выполняет команды

Напишем программу сортировки методом Пузырька на Python 3.

Задачи:

  1. Отсортировать список по возрастанию суммы цифр чисел
  2. Дан список целых чисел, состоящий из 30 элементов. Найти сумму пяти самых больших и пяти самых маленьких элементов списка.
Ссылка на основную публикацию
Adblock detector