Сортиране чрез пряка размяна

(метод на мехурчето)

При този метод на сортиране се сравняват всеки два съседни елемента и ако елементът с по-малък индекс има по-голяма стойност, местата им се разменят. Сравнението започва от последния към първия елемент на масива. При първото обхождане най-малкия елемент “изплува” на първо място в масива. При второто обхождане следващият по-големина елемент изплува и застава на втора позиция в масива. И така след n-1 обхождания масивът е подреден във възходящ ред.

Пример

Първо обхождане

i=0	44	44	44	44	44	44	44	6
i=1	55	55	55	55	55	55	6	44
i=2	12	12	12	12	12	6	55	55
i=3	42	42	42	42	6	12	12	12
i=4	94	94	94	6	42	42	42	42
i=5	18	18	6	94	94	94	94	94
i=6	6	6	18	18	18	18	18	18
i=7	67	67	67	67	67	67	67	67

Второ обхождане

i=0	6	6	6	6	6	6	6
i=1	44	44	44	44	44	44	12
i=2	55	55	55	55	55	12	44
i=3	12	12	12	12	12	55	55
i=4	42	42	42	18	18	18	18
i=5	94	94	18	42	42	42	42
i=6	18	18	94	94	94	94	94
i=7	67	67	67	67	67	67	67

Трето обхождане

i=0	6	6	6	6	6	6
i=1	12	12	12	12	12	12
i=2	44	44	44	44	44	18
i=3	55	55	55	55	18	44
i=4	18	18	18	18	55	55
i=5	42	42	42	42	42	42
i=6	94	67	67	67	67	67
i=7	67	94	94	94	94	94

Четвърто обхождане

i=0	6	6	6	6	6
i=1	12	12	12	12	12
i=2	18	18	18	18	18
i=3	44	44	44	44	42
i=4	55	55	55	42	44
i=5	42	42	42	55	55
i=6	67	67	67	67	67
i=7	94	94	94	94	94

Пето обхождане

i=0	6	6	6	6
i=1	12	12	12	12
i=2	18	18	18	18
i=3	42	42	42	42
i=4	44	44	44	44
i=5	55	55	55	55
i=6	67	67	67	67
i=7	94	94	94	94

Шесто обхождане

i=0	6	6	6
i=1	12	12	12
i=2	18	18	18
i=3	42	42	42
i=4	44	44	44
i=5	55	55	55
i=6	67	67	67
i=7	94	94	94

Седмо обхождане

i=0	6	6
i=1	12	12
i=2	18	18
i=3	42	42
i=4	44	44
i=5	55	55
i=6	67	67
i=7	94	94

Обхождането винаги започва от последния елемент.

За алгоритмичното решаване на задачата е необходимо да се организират 2 цикъла: външен цикъл, който да следи границата на подредения подмасив и вътрешен, в който да се извършва сравняването и размяната на елементите. Външния цикъл се контролира от стойността на индексната променлива i, която съдържа крайния индекс на подредената част на масива (началният е винаги 0- първия елемент на масива). Променливата i се мени от 0 до n-2. (Не забравяйте, че максималният индекс на масива е n-1.) Ако всичките n-1 елемента са подредени, следва, че и n-тия елемент е на мястото си.

Вътрешния цикъл се контролира от стойността на променливата j. В него се извършва сревнение и евентуална размяна на елементите с индекси j и j -1. Стойността на променливата j се мени в границите от n-1(последния елемент от масива) до i+1 (началния индекс на неподредения подмасив).

Размяната на стойностите на елементите се изпълнява в три стъпки. За целта се използва помощната променлива pom.

Блоковата схема на алгоритъма за сортиране по метода на мехурчето е показана на фиг.3, а програмата – на листинг 2.

Гранични случаи:

1. Първо обхождане: i=0

- начало на вътрешния цикъл - сравняват се n-1^-вия и n-2^-рия елемент.

- край на вътрешния цикъл - сравняват се i^-тия с i-1^-вия елемент на масива, т.е. елемента с индекс 1 и елемента с индекс 0.

Ако в условието за край на вътрешния цикъл беше записано j>=i вместо j>i, то щяха да се сравняват елементи с индекси 0 и -1, което е недопустимо.

2. Последно обхождане - i=(n-2). Вътрешния цикъл има само едно завъртане. Сравняват се елементите с индекси (n-2) и (n-1) - предпоследния и последния елемент от масива.

Външния цикъл можеше да има условие за изпълнение (i<n), но тогава при последното завъртане вътрешния цикъл не би се изпълнил нито веднъж. Началната стойност за j щеше да е j=n-1 и условието j>i (i=n-2) нямаше да е изпълнено.

//Листинг 2

# include <iostream.h>

void input(float a[100], int &n)

{

int i;

cout<<"n=";

for(i = 0; i<n;i++)

{

cout<<"a["<<i<<"]=";

cin>>a[i];

}

}

void output (float a[100], int n)

{

int i;

for(i=0;i<n;i++)

{

cout<<a[i]<<'\t';

}

}

void sort(float a[100], int n)

{

int i,j;

float x;

for(i=0;i<n-1;i++)

{

for(j=n-1;j>i;j--)

{

if(a[j]<a[j-1])

{

x=a[j];

a[j]=a[j-1];

a[j-1]=x;

}

}

}

}

void main(void)

{

int n;

float a[100];

input (a,n) ;

sort (a,n) ;

output (a,n) ;

}