Шта је врста мехурића?
Сортирање мехурића је алгоритам за сортирање који се користи за сортирање ставки листе у растућем редоследу поређењем две суседне вредности. Ако је прва вредност виша од друге вредности, прва вредност заузима другу позицију вредности, док друга вредност заузима прву позицију вредности. Ако је прва вредност нижа од друге вредности, тада се замена не врши.
Овај поступак се понавља све док се све вредности на листи не упореде и по потреби не замене. Свака итерација се обично назива пролазом. Број пролаза у сортирању облачића једнак је броју елемената на листи минус један.
У овом водичу за сортирање мехурића у Питхону научићете:
- Шта је врста мехурића?
- Примена алгоритма сортирања мехурића
- Оптимизовани алгоритам сортирања мехурића
- Визуелни приказ
- Примери Питхона
- Објашњење кода
- Предности сортирања мехурића
- Недостаци сортирања мехурића
- Анализа сложености сорте мехурића
Примена алгоритма сортирања мехурића
Разврстићемо имплементацију у три (3) корака, наиме проблем, решење и алгоритам који можемо користити за писање кода за било који језик.
Проблем
Списак предмета дат је насумичним редоследом и желели бисмо да их уредимо по редоследу
Размотрите следећу листу:
[21,6,9,33,3]
Раствор
Прелистајте листу упоређујући два суседна елемента и замењујући их ако је прва вредност већа од друге вредности.
Резултат би требао бити следећи:
[3,6,9,21,33]
Алгоритам
Алгоритам сортирања облачића ради на следећи начин
Корак 1) Добијте укупан број елемената. Добијте укупан број предмета на датој листи
Корак 2) Одредите број спољних додавања (н - 1) које треба извршити. Његова дужина је листа минус један
Корак 3) Извршите унутрашња додавања (н - 1) пута за спољни пролаз 1. Набавите вредност првог елемента и упоредите га са другом вредношћу. Ако је друга вредност мања од прве вредности, замените позиције
Корак 4) Понављајте кораке 3 док не дођете до спољног пролаза (н - 1). Набавите следећи елемент на листи, а затим понављајте поступак који је изведен у кораку 3 док све вредности не буду постављене у њихов исправан редослед узлазно.
Корак 5) Вратите резултат када су сва додавања завршена. Врати резултате сортиране листе
Корак 6) Оптимизујте алгоритам
Избегавајте непотребне унутрашње пролазе ако су листа или суседне вредности већ сортиране. На пример, ако наведена листа већ садржи елементе који су сортирани у растућем редоследу, онда можемо рано прекинути петљу.
Оптимизовани алгоритам сортирања мехурића
Подразумевано алгоритам сортирања облачића у Питхону упоређује све ставке на листи без обзира да ли је листа већ сортирана или не. Ако је дата листа већ сортирана, поређење свих вредности је губљење времена и ресурса.
Оптимизација сортирања облачића помаже нам да избегнемо непотребне понављања и уштедимо време и ресурсе.
На пример, ако су прва и друга ставка већ сортиране, нема потребе за итерацијом кроз остале вредности. Итерација се прекида, а следећа се започиње док се поступак не заврши, као што је приказано у доњем примеру сортирања облачића.
Оптимизација се врши помоћу следећих корака
Корак 1) Направите променљиву заставице која надгледа да ли је дошло до замене у унутрашњој петљи
Корак 2) Ако су вредности замењивале позиције, пређите на следећу итерацију
Корак 3) Ако предности нису замењене положајима, прекините унутрашњу петљу и наставите са спољном петљом.
Оптимизована сорта облачића је ефикаснија јер извршава само потребне кораке и прескаче оне који нису потребни.
Визуелни приказ
С обзиром на листу од пет елемената, следеће слике илуструју како се мехурић сортира кроз вредности приликом сортирања
Следећа слика приказује несортирану листу
Прво понављање
Корак 1)
Вредности 21 и 6 се упоређују како би се проверило која је већа од друге.
21 је веће од 6, тако да 21 заузима положај који заузима 6, док 6 заузима положај који је заузимао 21
Наша измењена листа сада изгледа као она горе.
Корак 2)
Упоређују се вредности 21 и 9.
21 је веће од 9, па замењујемо позиције 21 и 9
Нова листа је сада као горе
Корак 3)
Вредности 21 и 33 се упоређују да би се пронашла већа.
Вредност 33 је већа од 21, тако да не долази до замене.
Корак 4)
Вредности 33 и 3 се упоређују да би се пронашла већа.
Вредност 33 је већа од 3, па замењујемо њихове позиције.
Сортирана листа на крају прве итерације је попут оне горе
Друга понављања
Нова листа након друге итерације је следећа
Трећа понављања
Нова листа након треће итерације је следећа
Четврта понављања
Нова листа након четврте итерације је следећа
Примери Питхона
Следећи код показује како применити алгоритам сортирања облачића у Питхону.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Извршавање горњег програма сортирања облачића у Питхону даје следеће резултате
[6, 9, 21, 3, 33]
Објашњење кода
Објашњење програмског кода Питхон Буббле Сорт је следеће
ОВДЕ,
- Дефинише функцију бубблеСорт која прихвата параметарСек. Код не даје ништа.
- Добија дужину низа и додељује вредност променљивој н. Код не даје ништа
- Покреће петљу фор која покреће алгоритам сортирања облачића (н - 1) пута. Ово је спољна петља. Код не даје ништа
- Дефинише променљиву заставице која ће се користити за утврђивање да ли је дошло до замене или није. Ово је у сврху оптимизације. Код не даје ништа
- Покреће унутрашњу петљу која упоређује све вредности на листи од прве до последње. Код не даје ништа.
- Користи израз иф за проверу да ли је вредност на левој страни већа од вредности на непосредној десној страни. Код не даје ништа.
- Додељује вредност тхеСек [ј] привременој променљивој тмп ако услов процијени на тачно. Код не даје ништа
- Вредност тхеСек [ј + 1] додељује се положају тхеСек [ј]. Код не даје ништа
- Вредност променљиве тмп додељује се положајуСек [ј + 1]. Код не даје ништа
- Променљивој застави додељује се вредност 1 која означава да је дошло до замене. Код не даје ништа
- Користи израз иф за проверу да ли је вредност заставице променљиве 0. Код не даје ништа
- Ако је вредност 0, тада позивамо наредбу бреак која излази из унутрашње петље.
- Враћа вредност тхеСек након што је сортиран. Код даје сортирану листу.
- Дефинише променљиву ел која садржи листу случајних бројева. Код не даје ништа.
- Додељује вредност функције бубблеСорт променљивом резултату.
- Штампа вредност променљиве резултат.
Предности сортирања мехурића
Следе неке од предности алгоритма сортирања облачића
- То је лако разумети
- Изводи се врло добро када је листа већ или скоро сортирана
- Не захтева опсежну меморију.
- Лако је написати код за алгоритам
- Захтеви за простором су минимални у поређењу са другим алгоритмима за сортирање.
Недостаци сортирања мехурића
Следе неки од недостатака алгоритма за сортирање мехурића
- Не функционише добро приликом сортирања великих листа. Потребно је превише времена и ресурса.
- Углавном се користи у академске сврхе, а не у стварном свету.
- Број корака потребних за сортирање листе је реда бр. 2
Анализа сложености сорте мехурића
Постоје три врсте сложености:
1) Сложеност сортирања
Сложеност сортирања користи се за изражавање времена извршења и простора потребног за сортирање листе. Сортирање облачића чини (н - 1) итерација за сортирање листе где је н укупан број елемената на листи.
2) Временска сложеност
Временска сложеност сорте мехурића је О (н 2 )
Временске сложености могу се категорисати као:
- Најгори случај - овде је наведена листа у опадајућем редоследу. Алгоритам изводи максималан број извршавања који се изражава као [Биг-О] О (н 2 )
- Најбољи случај - ово се дешава када је наведена листа већ сортирана. Алгоритам изводи минимални број извршавања који се изражава као [Биг-Омега] Ω (н)
- Просечан случај - ово се дешава када је листа насумичним редоследом. Просечна сложеност је представљена као [Биг-тхета] ⊝ (н 2 )
3) Сложеност простора
Сложеност простора мери количину додатног простора потребног за сортирање листе. Сортирање облачића захтева само један (1) додатни простор за временску променљиву која се користи за замену вредности. Због тога има свемирску сложеност О (1).
Резиме
- Алгоритам сортирања облачића функционише тако што упоређује две суседне вредности и замењује их ако је вредност на левој страни мања од вредности на десној.
- Имплементација алгоритма сортирања облачића релативно је једноставна са Питхоном. Све што треба да користите су наредбе за петље и иф.
- Проблем који алгоритам сортирања облачића решава је узимање случајне листе предмета и претварање у уређену листу.
- Алгоритам сортирања облачића у структури података најбоље ради када је листа већ сортирана, јер изводи минималан број итерација.
- Алгоритам сортирања облачића не функционише добро када је листа обрнутим редоследом.
- Сорта мехурића има временску сложеност О (н 2 ) и свемирску сложеност О (1)
- Алгоритам сортирања мехурића је најприкладнији за академске сврхе, а не за стварне примене.
- Оптимизовано сортирање облачића чини алгоритам ефикаснијим прескакањем непотребних итерација при провери вредности које су већ сортиране.