http://poradumo.pp.ua

Online Журнал-Світ порад.
Головна сторінка
» » Методи сортування в програмуванні: сортування "бульбашкою"

Методи сортування в програмуванні: сортування "бульбашкою"

Сортування бульбашкою не тільки не вважається найшвидшим методом, більш того, вона замикає перелік самих повільних способів упорядкування. Проте і у неї є свої плюси. Так, сортування методом бульбашки - саме що ні на є логічне і природне рішення проблеми, якщо необхідно розставити елементи в певному порядку. Звичайна людина вручну, наприклад, скористається саме їм - просто по інтуїції.

Звідки взялося таке незвичайне назва?

Методи сортування в програмуванні: сортування "бульбашкою"

Назва методу придумали, використовуючи аналогію з повітряними бульбашками у воді. Це метафора. Подібно до того, як маленькі бульбашки повітря піднімаються нагору - адже їх щільність більше, ніж який-небудь рідини (в даному випадку - води), так і кожен елемент масиву, чим менше він за значенням, тим більше він поступово пробирається до початку переліку чисел.




Опис алгоритму

Сортування бульбашкою виконується наступним чином:

  • перший прохід: елементи масиву чисел беруться за два і також парами порівнюються. Якщо в якийсь двійці елементів перше значення виявляється більше другого, програма робить їх обмін місцями;
  • отже, найбільше число потрапляє в кінець масиву. У той час як всі інші елементи залишаються, як і були, в хаотичному порядку і вимагають ще сортування;
  • тому і необхідний другий прохід: проводиться він за аналогією з попереднім (вже описаним) і має число порівнянь - мінус один;
  • біля проходу номер три порівнянь на одиницю менше, ніж у другого, і на двійку, ніж у першого. І так далі;
  • підсумуємо, що кожен прохід має (всього значень у масиві, конкретне число) мінус (номер проходу) порівнянь.

Методи сортування в програмуванні: сортування "бульбашкою"




Ще коротше алгоритм майбутньої програми можна записати так:

  • масив чисел перевіряється до тих пір, поки не будуть знайдені будь-які два числа, причому друге з них зобов'язана бути більше першого;
  • неправильно розташовані по відношенню один до одного елементи масиву програма міняє місцями.

Псевдокод на основі описаного алгоритму

Найпростіша реалізація виконується так:

Процедура Sortirovka_Puzirkom ;

Початок

цикл для j від nachalnii_index до konechii_index ;

цикл для i від nachalnii_index до konechii_index-1 ;

якщо massiv[i]>massiv[i+1] (перший елемент більше другого), то:

(міняємо значення місцями);

Кінець

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

Потрібна реалізація краще. Наприклад, враховує обмін значень у масиві місцями:

Процедура Sortirovka_Puzirkom ;

Початок

sortirovka = true;

цикл поки sortirovka = true;

sortirovka = false;

цикл для i від nachalnii_index до konechii_index-1 ;

якщо massiv[i]>massiv[i+1] (перший елемент більше другого), то:

(міняємо елементи місцями);

sortirovka = true; (позначили, що обмін був вироблений).

Кінець.

Недоліки методу

Основний мінус - тривалість процесу. Скільки ж часу виконується алгоритм сортування бульбашкою?

Час виконання розраховується з квадрата кількості чисел в масиві - кінцевий результат пропорційний йому.

При найгіршому варіанті масив буде пройдено стільки ж разів, скільки у ньому елементів мінус одне значення. Так відбувається тому, що в остаточному підсумку залишається тільки один елемент, який не з чим порівнювати, і останній прохід по масиву стає марним дійством.


Крім того, ефективний метод сортування простими обмінами, як його ще називають, тільки для масивів невеликого розміру. Великі обсяги даних з його допомогою обробити не вийде: результатом стануть або помилки, або збій роботи програми.

Методи сортування в програмуванні: сортування "бульбашкою"

Переваги

Сортування бульбашкою досить проста для розуміння. У навчальних програмах технічних Вузів при вивченні впорядкування елементів масиву проходять в першу чергу. Метод легко реалізується як на мові програмування Delphi (Д (Делфі), так і на C/C++ (Сі/Сі плюс плюс), неймовірно простий алгоритм розташування значень у вірному порядку і на Pascal (Паскаль). Сортування бульбашкою ідеально підходить для початківців.

По причині недоліків алгоритм не застосовують у позанавчальних цілях.

Наочний принцип сортування

Початковий вигляд масиву 8224 744437 1 7

Крок 1 8224 744437 1 7

8224 74441 37 7

8224 74144 37 7

8224 17444 37 7

8221 47444 37 7

8122 47444 37 7

1822 47444 37 7

Крок 2 1822 47444 737

1822 4747 4437

1822 4774 4437

1822 4774 4437

184 22774 4437

148 22774 4437

Крок 3 148 22774 3744

148 22737 7444

148 22737 7444

148 72237 7444

147 82237 7444

Крок 4 147 82237 4474

147 82237 4474

147 82237 4474

147 82237 4474

Крок 5 147 82237 4474

147 82237 4474

147 82237 4474

Крок 6 147 82237 4474

147 82237 4474

Крок 7 147 82237 4474

Приклад сортування бульбашкою на мові Pascal

Методи сортування в програмуванні: сортування "бульбашкою"

Приклад:

const kol_mas=10;

var massiv:array[1kol_mas]of integer;

a, b, k: integer;

begin

writeln ('input', kol_mas, 'elements of array');

for a:=1 to kol_mas do readln( massiv[a]);

for a:=1 to kol_mas-1 do begin

for b:=a+1 to kol_mas do begin

if massiv[a]>massiv[b]then begin

k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;

end;

end;

end;

writeln ('after sort');

for a:=1 to kol_mas do writeln( massiv[a]);

end.

Приклад сортування бульбашкою на мові С (Сі)

Приклад:

#include

#include

int main(int argc, char* argv[])

{

int massiv[8]= {3669773 826812 18388},i, ff;

for (; ;){

ff = 0;

for (i = 7; i>0; i--){

if (massiv[i]< massiv[i-1]) {

swap (massiv[i],massiv[i-1]);

ff++;

}

}

if (ff == 0) break;

}

getch(); //затримка екрану

return 0;

}.

of your page -->

Популярні поради

загрузка...