Увод у алгоритам сортирања мехурића

Сортирање је једна од најосновнијих операција које можете применити на податке. Можете сортирати елементе у различитим програмским језицима помоћу различитих алгоритама за сортирање, попут брзог сортирања, мехурићастог сортирања, спајања сортирања, сортирања уметања итд. Сортирање мехурића је најједноставнији алгоритам међу свима њима.

У овом чланку ћете сазнати о раду алгоритма сортирања мехурића, псеудо кода сортирања облачића алгоритам, његова временска и просторна сложеност и његова примена у различитим програмским језицима попут Ц ++, Питхон, Ц и ЈаваСцрипт.

Како функционише алгоритам сортирања мехурића?

Сортирање мехурића је најједноставнији алгоритам сортирања који непрекидно корача кроз листу, упоређује суседне елементе и замењује их ако су у погрешном редоследу. Овај концепт се може ефикасније објаснити уз помоћ примера. Размотрите несортирани низ са следећим елементима: {16, 12, 15, 13, 19}.

Пример:

Овде се суседни елементи упоређују и ако нису у растућем редоследу, замењују се.

Псеудокод алгоритма сортирања мехурића

У псеудокоду, алгоритам сортирања облачића може се изразити као:

бубблеСорт (Арр [], величина)
// петља за приступ сваком елементу низа
за и = 0 до сизе-1 урадите:
// петља за упоређивање елемената низа
за ј = 0 до сизе-и-1 урадите:
// упоређивање суседних елемената
ако је Арр [ј]> Арр [ј + 1] онда
// замените их
свап (Арр [ј], Арр [ј + 1])
крај ако
крај за
крај за
крај

Горњи алгоритам обрађује сва поређења чак и ако је низ већ сортиран. Може се даље оптимизовати заустављањем алгоритма ако унутрашња петља није проузроковала замену. Ово ће смањити време извршавања алгоритма.

Дакле, псеудокод оптимизованог алгоритма мехурића сортирања може се изразити као:

бубблеСорт (Арр [], величина)
// петља за приступ сваком елементу низа
за и = 0 до сизе-1 урадите:
// проверавамо да ли долази до замене
замењено = нетачно
// петља за упоређивање елемената низа
за ј = 0 до сизе-и-1 урадите:
// упоређивање суседних елемената
ако је Арр [ј]> Арр [ј + 1] онда
// замените их
свап (Арр [ј], Арр [ј + 1])
замењен = тачно
крај ако
крај за
// ако ниједан елемент није замењен, то значи да је низ сада сортиран, прекините петљу.
ако (није замењен) онда
пауза
крај ако
крај за
крај

Сложеност времена и помоћни простор алгоритма сортирања мехурића

Најлошија временска сложеност алгоритма сортирања мехурића је О (н ^ 2). Појављује се када је низ у опадајућем редоследу и желите да га сортирате у растућем редоследу или обрнуто.

Временска сложеност алгоритма сортирања мехурића је О (н). Појављује се када је низ већ сортиран.

Повезан: Шта је Биг-О нотација?

Просечна временска сложеност алгоритма сортирања мехурића је О (н ^ 2). Појављује се када су елементи низа у помешаном редоследу.

Помоћни простор потребан за алгоритам сортирања облачића је О (1).

Ц ++ Примена алгоритма сортирања мехурића

Испод је примена Ц ++ алгоритма сортирања облачића:

// Ц ++ имплементација
// оптимизован алгоритам сортирања облачића
#инцлуде 
коришћење простора имена стд;
// Функција извођења сортирања мехурића
воид бубблеСорт (инт арр [], инт величина) {
// Петља за приступ сваком елементу низа
за (инт и = 0; и // Променљива за проверу да ли долази до замене
боол замењен = нетачно;
// петља за упоређивање два суседна елемента низа
за (инт ј = 0; ј // Упоређивање два суседна елемента низа
иф (арр [ј]> арр [ј + 1]) {
// Замените оба елемента ако јесу
// није у исправном редоследу
инт темп = арр [ј];
арр [ј] = арр [ј + 1];
арр [ј + 1] = темп;
замењено = тачно;
}
}
// Ако ниједан елемент није замењен, то значи да је низ сада сортиран,
// затим прекинемо петљу.
иф (сваппед == фалсе) {
пауза;
}
}
}
// Штампа елементе низа
воид принтАрраи (инт арр [], инт величина) {
за (инт и = 0; и цоут << арр [и] << "";
}
цоут << ендл;
}
инт маин () {
инт арр [] = {16, 12, 15, 13, 19};
// Проналажење дужине низа
инт сизе = сизеоф (арр) / сизеоф (арр [0]);
// Штампање датог несортираног низа
цоут << "Несортирани низ:" << ендл;
принтАрраи (арр, величина);
// Позивање функције бубблеСорт ()
бубблеСорт (арр, величина);
// Штампање сортираног низа
цоут << "Сортирани низ у растућем редоследу:" << ендл;
принтАрраи (арр, величина);
ретурн 0;
}

Излаз:

Несортирани низ: 
16 12 15 13 19 
Сортирани низ у растућем редоследу:
12 13 15 16 19

Питхон примена алгоритма сортирања мехурића

Испод је Питхон имплементација алгоритма Буббле Сорт:

# Питхон имплементација
# оптимизован алгоритам сортирања облачића
# Функција за извођење сортирања мехурића
деф бубблеСорт (арр, величина):
# Лооп за приступ сваком елементу листе
за и у опсегу (величина-1):
# Променљива за проверу да ли долази до замене
замењено = Нетачно
# петља за упоређивање два суседна елемента листе
за ј у опсегу (величина-и-1):
# Упоређивање два суседна елемента листе
ако је арр [ј]> арр [ј + 1]:
темп = арр [ј]
арр [ј] = арр [ј + 1]
арр [ј + 1] = темп
замењен = Тачно
# Ако ниједан елемент није замењен, то значи да је листа сада сортирана,
# онда прекини петљу.
ако је замењен == Нетачно:
пауза
# Штампа елементе листе
деф принтАрраи (арр):
за елемент у арр:
испис (елемент, крај = "")
испис ("")
арр = [16, 12, 15, 13, 19]
# Проналажење дужине листе
сизе = лен (арр)
# Штампање дате несортиране листе
принт ("Неразврстана листа:")
принтАрраи (арр)
# Позивање функције бубблеСорт ()
бубблеСорт (арр, величина)
# Штампање сортиране листе
принт ("Сортирана листа у растућем редоследу:")
принтАрраи (арр)

Излаз:

Несортирана листа:
16 12 15 13 19 
Сортирана листа у растућем редоследу:
12 13 15 16 19

Повезан: Како се користи за петље у Питхону

Ц Примена алгоритма сортирања мехурића

Испод је примена Ц алгоритма сортирања мехурића:

// Ц примена
// оптимизован алгоритам сортирања облачића
#инцлуде 
#инцлуде 
// Функција извођења сортирања мехурића
воид бубблеСорт (инт арр [], инт величина) {
// Петља за приступ сваком елементу низа
за (инт и = 0; и // Променљива за проверу да ли долази до замене
боол замењен = нетачно;
// петља за упоређивање два суседна елемента низа
за (инт ј = 0; ј // Упоређивање два суседна елемента низа
иф (арр [ј]> арр [ј + 1]) {
// Замените оба елемента ако јесу
// није у исправном редоследу
инт темп = арр [ј];
арр [ј] = арр [ј + 1];
арр [ј + 1] = темп;
замењено = тачно;
}
}
// Ако ниједан елемент није замењен, то значи да је низ сада сортиран,
// затим прекинемо петљу.
иф (сваппед == фалсе) {
пауза;
}
}
}
// Штампа елементе низа
воид принтАрраи (инт арр [], инт величина) {
за (инт и = 0; и принтф ("% д", арр [и]);
}
принтф ("\ ⁠н");
}
инт маин () {
инт арр [] = {16, 12, 15, 13, 19};
// Проналажење дужине низа
инт сизе = сизеоф (арр) / сизеоф (арр [0]);
// Штампање датог несортираног низа
принтф ("Несортирани низ: \ ⁠н");
принтАрраи (арр, величина);
// Позивање функције бубблеСорт ()
бубблеСорт (арр, величина);
// Штампање сортираног низа
принтф ("Сортирани низ у растућем редоследу: \ ⁠н");
принтАрраи (арр, величина);
ретурн 0;
}

Излаз:

Несортирани низ: 
16 12 15 13 19 
Сортирани низ у растућем редоследу: 
12 13 15 16 19

Имплементација ЈаваСцрипт алгоритма сортирања облачића

Испод је ЈаваСцрипт имплементација алгоритма Буббле Сорт:

// ЈаваСцрипт имплементација
// оптимизован алгоритам сортирања облачића
// Функција извођења сортирања мехурића
фунцтион бубблеСорт (арр, сизе) {
// Петља за приступ сваком елементу низа
за (нека је и = 0; и// Променљива за проверу да ли долази до замене
вар замењен = нетачно;
// петља за упоређивање два суседна елемента низа
за (нека ј = 0; ј// Упоређивање два суседна елемента низа
иф (арр [ј]> арр [ј + 1]) {
// Замените оба елемента ако јесу
// није у исправном редоследу
нека је темп = арр [ј];
арр [ј] = арр [ј + 1];
арр [ј + 1] = темп;
замењено = тачно;
}
// Ако ниједан елемент није замењен, то значи да је низ сада сортиран,
// затим прекинемо петљу.
иф (сваппед == фалсе) {
пауза;
}
}
}
}
// Штампа елементе низа
функција принтАрраи (арр, величина) {
за (нека је и = 0; идоцумент.врите (арр [и] + "");
}
доцумент.врите ("
")
}
вар арр = [16, 12, 15, 13, 19];
// Проналажење дужине низа
вар сизе = арр.ленгтх;
// Штампање датог несортираног низа
доцумент.врите ("Несортирани низ: 
");
принтАрраи (арр, величина);
// Позивање функције бубблеСорт ()
бубблеСорт (арр, величина);
// Штампање сортираног низа
доцумент.врите ("Сортирани низ у растућем редоследу: 
");
принтАрраи (арр, величина);

Излаз:

Несортирани низ:
16 12 15 13 19
Сортирани низ у растућем редоследу:
12 15 13 16 19

Сада разумете деловање алгоритма сортирања мехурића

Сортирање по мехурићима је најједноставнији алгоритам сортирања и углавном се користи за разумевање основа сортирања. Сортирање мехурића такође се може применити рекурзивно, али не пружа додатне предности за то.

Користећи Питхон, лако можете да примените алгоритам сортирања облачића. Ако вам Питхон није познат и желите да започнете своје путовање, почетак са „Хелло Ворлд“ скриптом је одличан избор.

Како започети са Питхоном користећи скрипту „Хелло Ворлд“

Питхон је један од најпопуларнијих програмских језика који се данас користи. Следите овај водич да бисте започели са вашом првом Питхон скриптом.

Прочитајте следеће

О аутору