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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 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])

Особенности алгоритма

  1. после каждой итерации только один элемент данных помещается в свою правильную позицию;
  2. сравнение и перестановка смежных элементов данных;
  3. в каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок;
  4. худший случай — когда элементы данных отсортированы в обратном порядке;
  5. лучший случай — когда элементы данных уже отсортированы в правильном порядке;
  6. легкость реализации.[Источник 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 }

Ссылки

  1. Анимированное сравнение алгоритмов сортировки
  2. http://sorting.at/ Анимация алгоритмов сортировки

Источники

  1. Джесси Рассел "Сортировка пузырьком" // VSD. Дата обновления: 15.06.2013. URL: https://dic.academic.ru/books.nsf/59611449/ ( дата обращения: 23.05.2018)
  2. Сортировка пузырьком // Википедия. [2018—2018]. Дата обновления: 27.05.2018. URL: https://ru.wikipedia.org/?oldid=92905311 (дата обращения: 27.05.2018).
  3. §11 Алгоритмы сортировки и поиска. Обобщенные алгоритмы sort и find// INF-W. Дата обновления:27.03.2017. URL:http://inf-w.ru/?page_id=5734#3 ( дата обращения: 25.05.2018)
  4. Глава 3. Метод грубой силы: Пузырьковая сортировка( Вильямс,2006)|pages=144—146]]// Wikidata. Дата обновления: 05.04.2006. URL: https://www.wikidata.org/wiki/Q21694522( Дата обращения: 15.05.2018).