Ввести целочисленный массив из N ‘элементов с клавиатуры. Отсортировать его по возрастанию методом пузырька.
Исходный код на языке C++
/* * Ввести целочисленный массив из N целых чисел. * Отсортировать этот массив по возрастанию методом пузырька */ #include using namespace std; int main() < int *arr; // указатель для выделения памяти под массив int size; // размер массива // Ввод количества элементов массива cout > size; if (size arr = new int[size]; // выделение памяти под массив // заполнение массива for (int i = 0; i < size; i++) < cout > arr[i]; > int temp; // временная переменная для обмена элементов местами // Сортировка массива пузырьком for (int i = 0; i < size — 1; i++) < for (int j = 0; j < size — i — 1; j++) < if (arr[j] >arr[j + 1]) < // меняем элементы местами temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; >> > // Вывод отсортированного массива на экран for (int i = 0; i < size; i++) < cout cout
Источник: code-live.ru
Сортировка пузырьком в python. Bubble sort in Python
Сортировка методом пузырька
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, то есть упорядочивания. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).
Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: «метод пузырька»?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно «всплывают» в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм и особенности этой сортировки таковы:
- При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и так далее. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
- Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
- При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
- На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
- В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
- После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно M-1 , где M – это количество элементов массива.
- Количество сравнений в каждом проходе равно m-i , где i – это номер прохода по массиву (первый, второй, третий и так далее).
- При обмене элементов массива обычно используется «буферная» (третья) переменная, куда временно помещается значение одного из элементов.
Программа на языке Паскаль:
const M = 10; var arr: array[1..M] of integer; i, j, k: integer; begin randomize; write(‘Исходный массив: ‘); for i := 1 to M do begin arr[i] := random(100); write(arr[i]:3); end; writeln; for i := 1 to M-1 do for j := 1 to M-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 M do write (arr[i]:3); writeln; end.
Пример выполнения программы:
Исходный массив: 42 32 52 82 15 3 19 62 76 41 Отсортированный: 3 15 19 32 41 42 52 62 76 82
Источник: pas1.ru
Сортировка пузырьком (Pascal)
Всем привет!
Сегодня мы разберем сортировку методом «пузырька». Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка — это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.
Существуют различные алгоритмы сортировки. Некоторые, хорошо сортируют большое количество элементов, другие, более эффективны при очень маленьком количестве элементов. Наш метод пузырька характерен:
- Простота реализации алгоритма
- Красивое название
- Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2 )
- Почти не применяется в реальной жизни (используется в основном в учебных целях)
Алгоритм: Берем элемент массива, сравниваем со следующим, если наш элемент, больше следующего элемента, то мы их меняем местами. После прохождения всего массива, мы можем быть уверены, что максимальный элемент будет «вытолкнут» — и стоять самым последним. Таким образом, один элемент у нас уже точно стоит на своём месте. Т.к. нам надо их все расположить на свои места, следовательно, мы должны повторить данную операцию, столько раз, сколько у нас элементов массива минус 1. Последний элемент встанет автоматически, если остальные стоят на своих местах.
Вернемся к нашему массиву : 3 1 4 2
Берем первый элемент «3» сравниваем со следующим «1». Т.к. «3» > «1», то меняем местами:
1 3 4 2
Теперь сравниваем «3» и «4», тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем «4» и «2». Четыре больше, чем два — значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло.
Где бы «4» (наш самый большой элемент) не находился — он всё равно, после прохождения циклом всего массива, будет последним. Аналогия — как пузырёк воздуха всплывает в воде — так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется «Пузырьковая сортировка». Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.
Сравниваем «1» и «3» — ничего не меняем.
Сравниваем «3» и «2» — Три больше двух, значит меняем местами. Получается : 1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла — значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй — видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.
Теперь осталось запрограммировать данный алгоритм на языке Pascal.
const n = 4; var i, j, k :integer; m:array[1..n] of integer; begin Writeln(‘Введите массив:’); for i:=1 to n do begin Writeln(i, ‘ элемент:’); Readln(m[i]); end; for i:=1 to n-1 do begin for j:=1 to n-i do begin if m[j]>m[j+1] then begin k:=m[j]; m[j]:=m[j+1]; m[j+1]:=k; end; end; end; for i:=1 to n do Write(m[i], ‘ ‘); end.
Вот результат:
А вот видеоурок
Источник: code-enjoy.ru