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

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

Идея алгоритма

Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов n которого равно 5: 8, 2, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений.Вначале сравниваются два первых элемента последовательности: 8 и 2, так как значение первого элемента больше значения второго, т. е. 8>2, они меняются местами. Далее, сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется n*(n-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок. .

Алгоритм

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

Псевдокод сортировки пузырьком:

 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. легкость реализации..

Программа

Программа, в которой сначала необходимо ввести размер одномерного массива, после чего массив заполняется случайными числами и сортируется методом пузырька // 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/ Анимация алгоритмов сортировки