Сортировка пузырьком
Последнее изменение этой страницы: 18:53, 22 июня 2018.
Сортировка пузырьком (обменная сортировка) – простой в реализации алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко. Хотя этот метод сортировки лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка[Источник 1].
Идея алгоритма
Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов n которого равно 5: 8, 2, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений.Вначале сравниваются два первых элемента последовательности: 8 и 2, так как значение первого элемента больше значения второго, т. е. 8>2, они меняются местами. Далее, сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется n*(n-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок. [Источник 2].
Алгоритм
Принцип действий прост: обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, вставляя найденные максимумы в конец[Источник 3].
Псевдокод сортировки пузырьком:
function bubbleSort(a):
for i = 0 to n - 2
for j = 0 to n - 2
if a[j] > a[j + 1]
swap(a[j], a[j + 1])
Особенности алгоритма
- после каждой итерации только один элемент данных помещается в свою правильную позицию;
- сравнение и перестановка смежных элементов данных;
- в каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок;
- худший случай — когда элементы данных отсортированы в обратном порядке;
- лучший случай — когда элементы данных уже отсортированы в правильном порядке;
- легкость реализации.[Источник 4].
Программа
Программа, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька // bu_sort.cpp: определяет точку входа для консольного приложения.
1 #include "stdafx.h"
2 #include <iostream>
3 using std::cout;
4 using std::cin;
5 using std::endl;
6
7 const int n = 100;
8
9 void Swap(int &x,int &y)
10 {
11 x = x + y;
12 y = x - y;
13 x = x - y;
14 }
15
16 void Bubble_Sort(int *a, int LeanghtArray)
17 {
18 for (int i = 1; i < LeanghtArray-1; ++i){
19 for (int i2 = 1; i2 < LeanghtArray-1; ++i2){
20 if (a[i2] > a[i2+1]){
21 Swap(a[i2], a[i2+1]);
22 }
23 }
24 }
25 }
26
27
28 int _tmain(int argc, _TCHAR* argv[])
29 {
30 int a[n], a1[n], i, i2;
31 for (int i = 1; i < n; i++){ a[i] = rand(); a1[i] = a[i]; }
32
33 Bubble_Sort(a, n);
34
35 for (int i = 1; i < n; i++){ cout << a[i] <<" "<<a1[i]<<endl; }
36 cin >> i;
37 return 0;
38 }
Ссылки
- Анимированное сравнение алгоритмов сортировки
- http://sorting.at/ Анимация алгоритмов сортировки
Источники
- ↑ Джесси Рассел "Сортировка пузырьком" // VSD. Дата обновления: 15.06.2013. URL: https://dic.academic.ru/books.nsf/59611449/ ( дата обращения: 23.05.2018)
- ↑ Сортировка пузырьком // Википедия. [2018—2018]. Дата обновления: 27.05.2018. URL: https://ru.wikipedia.org/?oldid=92905311 (дата обращения: 27.05.2018).
- ↑ §11 Алгоритмы сортировки и поиска. Обобщенные алгоритмы sort и find// INF-W. Дата обновления:27.03.2017. URL:http://inf-w.ru/?page_id=5734#3 ( дата обращения: 25.05.2018)
- ↑ Глава 3. Метод грубой силы: Пузырьковая сортировка( Вильямс,2006)|pages=144—146]]// Wikidata. Дата обновления: 05.04.2006. URL: https://www.wikidata.org/wiki/Q21694522( Дата обращения: 15.05.2018).
ISSN 2542-0356
Следуй за Полисом
Оставайся в курсе последних событий
Лицензия
Если не указано иное, содержание этой страницы доступно по лицензии Creative Commons «Attribution-NonCommercial-NoDerivatives» 4.0, а примеры кода – по лицензии Apache 2.0. Подробнее см. Условия использования.