Обмінне сортування

Метод добре відомий також під назвою (російською мовою)«пузырьковая сортировка». Тут менші значення елементів подібно до легких бульбашок повітря піднімаються вгору. Метод базується на порівнянні пари сусідніх елементів та перестановці їх в потрібному порядку. Сортування вважається закінченим, якщо в ході перегляду масиву не було здійснено жодної перестановки.

Розглянемо масив А= (3, 0, 8, 2, -4), що треба упорядкувати в порядку зростання значень елементів. Порівнюючи сусідні елементи (a_i та а_i+1), бачимо, що їх необхідно поміняти місцями, якщо а_i > а_i+1. Масив буде змінюватися при кожному його перегляді. Звернемо увагу на те, як найменший елемент (-4) повільно переміщується в початок масиву.

В результаті одержимо: після першого перегляду: А=(0, 3, 2, -4, 8); після другого перегляду: А=(0, 2, -4, 3, 8); після третього перегляду: А=(0, -4, 2, 3, 8); після четвертого перегляду: А=(-4, 0, 2, 3, 8).

При перегляді масиву цикл треба завершати на передостанньому елементі, тому що порівнюються i-й та (i+1)-й елементи. Для упорядкування масиву A(N) достатньо N-1 послідовних переглядів. Дійсно, в розглянутому масиві А(5) із останнього місця найменший елемент перемістився на перше місце за чотири перегляди масиву.

Таким чином, алгоритм сортування складається з двох циклів: внутрішнього, в якому проводиться перестановка необхідних елементів, та зовнішнього, що організує повторні перегляди масиву (рис. 7.1). Крім того, необхідно передбачити також виведення елементів вхідного та упорядкованого масивів.

Існує декілька модифікацій наведеного методу, які дозволяють зменшити кількість перевірок та час роботи програми. Наприклад, ввівши допоміжну змінну («прапорець»), можна перевірити настання моменту скінчення сортування (рис. 7.2).

При упорядкуванні за зростанням у циклі перевіряється умова a_i > a_i+1. Неважко побачити, що при упорядкуванні за спаданням треба перевіряти умову a_i < a_j+1.

Приклад 1. Задано масив D(M) та натуральні числа L, N. Упорядкувати за спаданням значень елементи, розміщені між елементами з індексом L та індексом N. Для розв’язання задачі застосуємо метод «прапорця».

#include <stdio.h>

main()

{

float d[100];

int i,m,n,l,flag;

float tmp;

m2:printf(“Ведіть розмірність масиву m та індекси l та n”);

scanf(“%d%d%d”, &m, &l, &n);

if(l>=1&&n>l&&n<=m)

{

for(i=0;i<m;i++) scanf(“%g”, &d[i]);

printf(“Неупорядкований масив:”);

for(i=0;i<m;i++) printf(“%g”,d[i]);

printf(“\n”);

m1:flag=1;

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

{

if(d[i]<d[i+1])

{

tmp=d[i];d[i]=d[i+1];d[i+1]=tmp;flag=0;

}

}

if(flag==0) goto m1;

printf(“Упорядкований масив:”);

for(i=0;i<m;i++) printf(“%d”,d[i]);

}

else goto m2;

return 0;

}

Приклад 2. Задано масив A(N). Упорядкувати його в порядку зростання значень елементів. Блок-схема алгоритму подана на рис. 7.3.

#include <stdio.h>

main()

{

int a[100];

int i,j,n,tmp;

printf(“Ведіть розмірність масиву”);

scanf(“%d”,&n);

for(i=0;i<n;i++) scanf(“%g”, &a[i]);

printf(“Неупорядкований масив:”);

for(i=0;i<n;i++) printf(“%g”,a[i]);

printf(“\n”);

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

for(j=i;j<10;j++){

if(a[j]<a[j+1]){tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;}

}

}

printf(“Упорядкований масив:”);

for(i=0;i<n;i++) printf(“%d”,a[i]);

printf(“\n”);

return 0;

}