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

Сортировка простыми обменами, сортиро́вка пузырько́м Английский язык bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: Θ$$(n^2)$$.

Алгоритм:

1) Последовательно бежим по массиву и сравниваем два соседних элемента, если порядок не верный то меняем их местами.

2) Повторять проходы на один меньше, чем кол-во элементов в массиве или пока не окажеться, что за проход не произведено ни одной замены.

Просмотрим алгоритм на примере:

Отсортируем массив: 524613 где каждая цифра это элемент массива.

Начало цикла, в массиве 524613 нет отсортированных чисел:

1) Первый проход:

524613->254613->245613->245613->245163->245136

Мы бежим по массиву и меняем элементы местами, которые находятся рядом друг с другом и не соответствуют порядку сортировки. Первый шаг это цифры 5 и 2, второй 5 и 4, третий 6 и 5, четвёртый 6 и 1, пятый 6 и 3.

2) Второй проход.

245136->245136->245136->241536->241356->241356

3) Третий проход.

241356->241356->214356->213456->213456->213456

4) Четвёртый проход.

213456->123456->123456->123456->123456->123456

После первого шага видно, что массив отсортирован, но условия выхода из сортировки ещё нет сказано, что не должно проходить ни одного изменения, или шаг должен быть на один меньше, чем кол-во элементов в массиве.

5) Пятый проход финальный.

123456->123456->123456->123456->123456->123456

Сразу удовлетворилось два условия выхода, небыло произведено ни одного изменения и проход по счёту равен количеству элементов в массиве минус 1.

Реализация алгоритма на языке Паскаль:

program BubbleSort;
Const
  N=100;

procedure Swap(var X,Y:Real);
begin
  X:=X+Y;
  Y:=X-Y;
  X:=X-Y;
end;

Procedure Bubble_Sort (var a : array of real; LengthArray :Integer);
var i,i2:integer;
begin
 for i:=1 to LengthArray-1 do
  for i2:=1 to LengthArray-2 do
   if a[i2+1]<a[i2] then Swap(a[i2],a[i2+1]);
end;

var
a,a1 : array [1..N] of real;
i: integer;

begin
 for i:=1 to N do a[i]:=Random(100);
 a1:=a;

 Bubble_Sort(a1,N);


 for i:=1 to N do writeln(a[i]:7:0,'  ',a1[i]:7:0);

end.

program BubbleSort;

Const

N=100;

procedure Swap(var X,Y:Real);

begin

X:=X+Y;

Y:=X-Y;

X:=X-Y;

end;

Procedure Bubble_Sort (var a : array of real; LengthArray :Integer);

var i,i2:integer;

begin

for i:=1 to LengthArray-1 do

for i2:=1 to LengthArray-2 do

if a[i2+1]<a[i2] then Swap(a[i2],a[i2+1]);

end;

var

a,a1 : array [1..N] of real;

i: integer;

begin

for i:=1 to N do a[i]:=Random(100);

a1:=a;

Bubble_Sort(a1,N);

for i:=1 to N do writeln(a[i]:7:0,' ',a1[i]:7:0);

end.

Реализация алгоритма на языке C:

#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

const int n = 100;

void Swap(int &x,int &y)
{
	x = x + y;
	y = x - y;
	x = x - y;
}

void Bubble_Sort(int *a, int LeanghtArray)
{
	for (int i = 1; i < LeanghtArray-1; ++i){
		for (int i2 = 1; i2 < LeanghtArray-1; ++i2){
			if (a[i2] > a[i2+1]){ 
				Swap(a[i2], a[i2+1]);
			}
		}
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	int a[n], a1[n], i, i2;
	for (int i = 1; i < n; i++){ a[i] = rand(); a1[i] = a[i]; }
	
	Bubble_Sort(a, n);
	
	for (int i = 1; i < n; i++){ cout << a[i] <<" "<<a1[i]<<endl; }
	cin >> i;
	return 0;
}

#include "stdafx.h"

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

const int n = 100;

void Swap(int &x,int &y)

{

x = x + y;

y = x - y;

x = x - y;

}

void Bubble_Sort(int *a, int LeanghtArray)

{

for (int i = 1; i < LeanghtArray-1; ++i){

for (int i2 = 1; i2 < LeanghtArray-1; ++i2){

if (a[i2] > a[i2+1]){

Swap(a[i2], a[i2+1]);

}

int _tmain(int argc, _TCHAR* argv[])

{

int a[n], a1[n], i, i2;

for (int i = 1; i < n; i++){ a[i] = rand(); a1[i] = a[i]; }

Bubble_Sort(a, n);

for (int i = 1; i < n; i++){ cout << a[i] <<" "<<a1[i]<<endl; }

cin >> i;

return 0;

}

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

Алгоритм:

Просмотрим алгоритм на примере:

Реализация алгоритма на языке Паскаль:

Реализация алгоритма на языке C:

Комментарии:

Добавить комментарий Отменить ответ