Въведение в алгоритъма за сортиране на балончета

Сортирането е една от най-основните операции, които можете да приложите към данните. Можете да сортирате елементи на различни езици за програмиране, като използвате различни алгоритми за сортиране като Бързо сортиране, Сортиране с балончета, Сливане на сортиране, Сортиране при вмъкване и др. Bubble Sort е най-простият алгоритъм сред всички тези.

В тази статия ще научите за работата на алгоритъма Bubble Sort, псевдокода на Bubble Sort алгоритъм, неговата времева и пространствена сложност и прилагането му в различни езици за програмиране като C ++, Python, C и JavaScript.

Как работи алгоритъмът за сортиране на балончета?

Bubble Sort е най-простият алгоритъм за сортиране, който многократно преминава през списъка, сравнява съседни елементи и ги разменя, ако са в грешен ред. Тази концепция може да бъде обяснена по-ефективно с помощта на пример. Помислете за несортиран масив със следните елементи: {16, 12, 15, 13, 19}.

Пример:

Тук съседните елементи се сравняват и ако не са във възходящ ред, те се разменят.

Псевдокод на алгоритъма за сортиране на балончета

В псевдокод, алгоритъмът за сортиране на балончета може да бъде изразен като:

bubbleSort (Arr [], размер)
// цикъл за достъп до всеки елемент на масив
за i = 0 до размер-1 направете:
// цикъл за сравняване на елементи от масив
за j = 0 до size-i-1 направете:
// сравняваме съседните елементи
ако Arr [j]> Arr [j + 1] тогава
// разменете ги
суап (Arr [j], Arr [j + 1])
край ако
край за
край за
край

Горният алгоритъм обработва всички сравнения, дори ако масивът вече е сортиран. Той може да бъде оптимизиран допълнително чрез спиране на алгоритъма, ако вътрешният цикъл не е причинил суап. Това ще намали времето за изпълнение на алгоритъма.

По този начин псевдокодът на оптимизирания алгоритъм за сортиране на балончета може да бъде изразен като:

bubbleSort (Arr [], размер)
// цикъл за достъп до всеки елемент на масив
за i = 0 до размер-1 направете:
// проверяваме дали се извършва размяна
разменен = невярно
// цикъл за сравняване на елементи от масив
за j = 0 до size-i-1 направете:
// сравняваме съседните елементи
ако Arr [j]> Arr [j + 1] тогава
// разменете ги
суап (Arr [j], Arr [j + 1])
разменен = вярно
край ако
край за
// ако не са разменени елементи, това означава, че масивът е сортиран сега, прекъснете цикъла.
ако (не е заменен) тогава
почивка
край ако
край за
край

Сложност на времето и помощно пространство на алгоритъма за сортиране на балончета

Сложността във времето в сложността на алгоритъма за сортиране на балончета е O (n ^ 2). Това се случва, когато масивът е в низходящ ред и искате да го сортирате във възходящ ред или обратно.

Сложността на алгоритъма за сортиране на мехурчета в най-добрия случай е O (n). Това се случва, когато масивът вече е сортиран.

Свързани: Какво е Big-O нотация?

Сложността на алгоритъма за сортиране на балончета в средния случай е O (n ^ 2). Това се случва, когато елементите на масива са в объркан ред.

Помощното пространство, необходимо за алгоритъма за сортиране на балончета, е O (1).

C ++ Внедряване на алгоритъма за сортиране на балончета

По-долу е C ++ изпълнението на алгоритъма Bubble Sort:

// C ++ изпълнение на
// оптимизиран алгоритъм за сортиране на балончета
#include 
използване на пространство от имена std;
// Функция за извършване на сортиране на балончета
void bubbleSort (int arr [], int size) {
// Цикъл за достъп до всеки елемент от масива
за (int i = 0; i // Променлива за проверка дали се извършва размяна
bool разменен = false;
// цикъл за сравняване на два съседни елемента от масива
за (int j = 0; j // Сравняване на два съседни елемента от масив
ако (arr [j]> arr [j + 1]) {
// Разменете и двата елемента, ако са
// не в правилен ред
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
разменен = вярно;
}
}
// Ако не са разменени елементи, това означава, че масивът е сортиран сега,
// след това прекъсваме цикъла.
ако (разменен == невярно) {
почивка;
}
}
}
// Отпечатва елементите на масива
void printArray (int arr [], int size) {
за (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Намиране на дължината на масива
int size = sizeof (arr) / sizeof (arr [0]);
// Печат на дадения несортиран масив
cout << "Несортиран масив:" << endl;
printArray (arr, размер);
// Извикване на функцията bubbleSort ()
bubbleSort (arr, размер);
// Печат на сортирания масив
cout << "Сортиран масив във възходящ ред:" << endl;
printArray (arr, размер);
връщане 0;
}

Изход:

Несортиран масив: 
16 12 15 13 19 
Сортиран масив във възходящ ред:
12 13 15 16 19

Прилагане на Python на алгоритъма за сортиране на балончета

По-долу е внедряването на Python на алгоритъма за сортиране на балончета:

# Внедряване на Python на
# оптимизиран алгоритъм за сортиране на балончета
# Функция за извършване на сортиране на балончета
def bubbleSort (arr, размер):
# Цикъл за достъп до всеки елемент от списъка
за i в обхват (размер-1):
# Променлива, за да се провери дали се сменя
разменен = Невярно
# цикъл за сравняване на два съседни елемента от списъка
за j в обхват (размер-i-1):
# Сравняване на два съседни елемента от списъка
ако arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = темп
разменен = Вярно
# Ако не са разменени елементи, това означава, че списъкът е сортиран сега,
# след това прекъснете цикъла.
ако е разменен == False:
почивка
# Отпечатва елементите от списъка
def printArray (arr):
за елемент в arr:
печат (елемент, край = "")
печат ("")
arr = [16, 12, 15, 13, 19]
# Намиране на дължината на списъка
размер = len (arr)
# Отпечатване на дадения несортиран списък
print ("Несортиран списък:")
printArray (arr)
# Извикване на функцията bubbleSort ()
bubbleSort (arr, размер)
# Печат на сортирания списък
print ("Сортиран списък във възходящ ред:")
printArray (arr)

Изход:

Несортиран списък:
16 12 15 13 19 
Сортиран списък във възходящ ред:
12 13 15 16 19

Свързани: Как да използвам за цикли в Python

C Прилагане на алгоритъма за сортиране на балончета

По-долу е C реализацията на алгоритъма за сортиране на балончета:

// C изпълнение на
// оптимизиран алгоритъм за сортиране на балончета
#include 
#include 
// Функция за извършване на сортиране на балончета
void bubbleSort (int arr [], int size) {
// Цикъл за достъп до всеки елемент от масива
за (int i = 0; i // Променлива за проверка дали се извършва размяна
bool разменен = false;
// цикъл за сравняване на два съседни елемента от масива
за (int j = 0; j // Сравняване на два съседни елемента от масив
ако (arr [j]> arr [j + 1]) {
// Разменете и двата елемента, ако са
// не в правилен ред
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
разменен = вярно;
}
}
// Ако не са разменени елементи, това означава, че масивът е сортиран сега,
// след това прекъсваме цикъла.
ако (разменен == невярно) {
почивка;
}
}
}
// Отпечатва елементите на масива
void printArray (int arr [], int size) {
за (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Намиране на дължината на масива
int size = sizeof (arr) / sizeof (arr [0]);
// Печат на дадения несортиран масив
printf ("Несортиран масив: \ ⁠n");
printArray (arr, размер);
// Извикване на функцията bubbleSort ()
bubbleSort (arr, размер);
// Печат на сортирания масив
printf ("Сортиран масив във възходящ ред: \ ⁠n");
printArray (arr, размер);
връщане 0;
}

Изход:

Несортиран масив: 
16 12 15 13 19 
Сортиран масив във възходящ ред: 
12 13 15 16 19

Прилагане на JavaScript на алгоритъма за сортиране на балончета

По-долу е дадено изпълнението на JavaScript на алгоритъма Bubble Sort:

// JavaScript изпълнение на
// оптимизиран алгоритъм за сортиране на балончета
// Функция за извършване на сортиране на балончета
функция bubbleSort (arr, размер) {
// Цикъл за достъп до всеки елемент от масива
за (нека i = 0; i// Променлива за проверка дали се извършва размяна
var swap = false;
// цикъл за сравняване на два съседни елемента от масива
за (нека j = 0; j// Сравняване на два съседни елемента от масив
ако (arr [j]> arr [j + 1]) {
// Разменете и двата елемента, ако са
// не в правилен ред
нека temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
разменен = вярно;
}
// Ако не са разменени елементи, това означава, че масивът е сортиран сега,
// след това прекъсваме цикъла.
ако (разменен == невярно) {
почивка;
}
}
}
}
// Отпечатва елементите на масива
функция printArray (arr, размер) {
за (нека i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Намиране на дължината на масива
var размер = arr.length;
// Печат на дадения несортиран масив
document.write ("Несортиран масив: 
");
printArray (arr, размер);
// Извикване на функцията bubbleSort ()
bubbleSort (arr, размер);
// Печат на сортирания масив
document.write ("Сортиран масив във възходящ ред: 
");
printArray (arr, размер);

Изход:

Несортиран масив:
16 12 15 13 19
Сортиран масив във възходящ ред:
12 15 13 16 19

Сега разбирате как работи алгоритъмът за сортиране на балончета

Bubble Sort е най-простият алгоритъм за сортиране и се използва главно за разбиране на основите на сортирането. Bubble Sort също може да се прилага рекурсивно, но не предоставя допълнителни предимства за това.

Използвайки Python, можете да внедрите алгоритъма Bubble Sort с лекота. Ако не сте запознати с Python и искате да започнете пътуването си, започването със скрипт "Hello World" е чудесен избор.

Как да започнем с Python, използвайки скрипт "Hello World"

Python е един от най-популярните езици за програмиране, който се използва днес. Следвайте този урок, за да започнете с първия си Python скрипт.

Прочетете Напред

За автора