Какво е сортиране на балончета?
Bubble Sort е алгоритъм за сортиране, използван за сортиране на елементи от списъка във възходящ ред чрез сравняване на две съседни стойности. Ако първата стойност е по-висока от втората стойност, първата стойност заема втората позиция на стойност, докато втората стойност заема първата позиция на стойността. Ако първата стойност е по-ниска от втората стойност, тогава не се извършва размяна.
Този процес се повтаря, докато всички стойности в списъка бъдат сравнени и разменени, ако е необходимо. Всяка итерация обикновено се нарича пропуск. Броят на проходите при сортиране на балончета е равен на броя на елементите в списъка минус един.
В този урок за сортиране на балончета в Python ще научите:
- Какво е сортиране на балончета?
- Прилагане на алгоритъма за сортиране на балончета
- Оптимизиран алгоритъм за сортиране на балончета
- Визуално представяне
- Примери за Python
- Обяснение на кода
- Предимства при сортиране на балончета
- Недостатъци при сортиране на балончета
- Анализ на сложността на сортирането на мехурчета
Прилагане на алгоритъма за сортиране на балончета
Ще разделим внедряването на три (3) стъпки, а именно проблема, решението и алгоритъма, който можем да използваме за писане на код за всеки език.
Проблемът
Списък на артикулите е даден в произволен ред и ние бихме искали да подредим елементите по ред
Обмислете следния списък:
[21,6,9,33,3]
Решението
Повтаряйте списъка, сравнявайки два съседни елемента и ги разменяйте, ако първата стойност е по-висока от втората стойност.
Резултатът трябва да бъде както следва:
[3,6,9,21,33]
Алгоритъм
Алгоритъмът за сортиране на балончета работи по следния начин
Стъпка 1) Вземете общия брой елементи. Вземете общия брой елементи в дадения списък
Стъпка 2) Определете броя на външните проходи (n - 1), които трябва да се извършат. Дължината му е списък минус един
Стъпка 3) Изпълнете вътрешни проходи (n - 1) пъти за външен пропуск 1. Вземете стойността на първия елемент и го сравнете с втората стойност. Ако втората стойност е по-малка от първата, разменете позициите
Стъпка 4) Повторете стъпки 3 преминавания, докато достигнете външния проход (n - 1). Вземете следващия елемент в списъка, след това повторете процеса, извършен в стъпка 3, докато всички стойности бъдат поставени в правилния им възходящ ред.
Стъпка 5) Върнете резултата, когато всички преминавания са направени. Върнете резултатите от сортирания списък
Стъпка 6) Оптимизиране на алгоритъма
Избягвайте ненужните вътрешни пропуски, ако списъкът или съседните стойности вече са сортирани. Например, ако предоставеният списък вече съдържа елементи, които са сортирани във възходящ ред, тогава можем да прекъснем цикъла по-рано.
Оптимизиран алгоритъм за сортиране на балончета
По подразбиране алгоритъмът за сортиране на балончета в Python сравнява всички елементи в списъка, независимо дали списъкът вече е сортиран или не. Ако даденият списък вече е сортиран, сравняването на всички стойности е загуба на време и ресурси.
Оптимизирането на сортирането на балончета ни помага да избегнем ненужни повторения и да спестим време и ресурси.
Например, ако първият и вторият елемент вече са сортирани, тогава няма нужда да преглеждате останалите стойности. Итерацията се прекратява и следващата се инициира, докато процесът завърши, както е показано в долния пример за сортиране на балончета.
Оптимизацията се извършва, като се използват следните стъпки
Стъпка 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, така че разменяме техните позиции.
Сортираният списък в края на първата итерация е като този по-горе
Второ повторение
Новият списък след втората итерация е както следва
Трета итерация
Новият списък след третата итерация е както следва
Четвърто повторение
Новият списък след четвъртата итерация е както следва
Примери за Python
Следващият код показва как да внедрите алгоритъма за сортиране на балончета в Python.
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)
Изпълнението на горната програма за сортиране на балончета в Python води до следните резултати
[6, 9, 21, 3, 33]
Обяснение на кода
Обяснението на програмния код на Python Bubble Sort е както следва
ТУК,
- Определя функция bubbleSort, която приема параметър theSeq. Кодът не извежда нищо.
- Получава дължината на масива и присвоява стойността на променлива n. Кодът не извежда нищо
- Стартира цикъл for, който изпълнява алгоритъма за сортиране на балончета (n - 1) пъти. Това е външният контур. Кодът не извежда нищо
- Определя променлива на флаг, която ще се използва, за да се определи дали е имало суап или не. Това е с цел оптимизация. Кодът не извежда нищо
- Стартира вътрешния цикъл, който сравнява всички стойности в списъка от първата до последната. Кодът не извежда нищо.
- Използва оператора if, за да провери дали стойността от лявата страна е по-голяма от тази от непосредствената дясна страна. Кодът не извежда нищо.
- Присвоява стойността на theSeq [j] на временна променлива tmp, ако условието оценява на true. Кодът не извежда нищо
- Стойността на theSeq [j + 1] се присвоява на позицията на theSeq [j]. Кодът не извежда нищо
- Стойността на променливата tmp се присвоява на позицията theSeq [j + 1]. Кодът не извежда нищо
- На променливата на флага се присвоява стойността 1, за да покаже, че е извършена размяна. Кодът не извежда нищо
- Използва оператор if, за да провери дали стойността на флага на променливата е 0. Кодът не извежда нищо
- Ако стойността е 0, тогава извикваме оператора break, който излиза от вътрешния цикъл.
- Връща стойността на theSeq, след като е сортирана. Кодът извежда сортирания списък.
- Определя променлива el, която съдържа списък на случайни числа. Кодът не извежда нищо.
- Присвоява стойността на функцията bubbleSort на променлив резултат.
- Отпечатва стойността на резултата от променливата.
Предимства при сортиране на балончета
Следват някои от предимствата на алгоритъма за сортиране на балончета
- Лесно е да се разбере
- Той се представя много добре, когато списъкът е вече или почти сортиран
- Не изисква обширна памет.
- Лесно е да напишете кода за алгоритъма
- Изискванията за пространство са минимални в сравнение с други алгоритми за сортиране.
Недостатъци при сортиране на балончета
Следват някои от недостатъците на алгоритъма за сортиране на балончета
- Не се представя добре при сортиране на големи списъци. Отнема твърде много време и ресурси.
- Използва се най-вече за академични цели, а не за реалното приложение.
- Броят стъпки, необходими за сортиране на списъка, е от порядъка n 2
Анализ на сложността на сортирането на мехурчета
Има три вида сложност са:
1) Сортирай сложността
Сложността на сортирането се използва за изразяване на времето за изпълнение и пространството, което е необходимо за сортиране на списъка. Сортирането на балончета прави (n - 1) итерации за сортиране на списъка, където n е общият брой елементи в списъка.
2) Сложност във времето
Сложността във времето на сорта балон е O (n 2 )
Сложността във времето може да бъде категоризирана като:
- Най-лошият случай - тук предоставяният списък е в низходящ ред. Алгоритъмът изпълнява максималния брой изпълнения, който се изразява като [Big-O] O (n 2 )
- Най-добрият случай - това се случва, когато предоставеният списък вече е сортиран. Алгоритъмът изпълнява минималния брой изпълнения, който се изразява като [Big-Omega] Ω (n)
- Среден случай - това се случва, когато списъкът е в произволен ред. Средната сложност е представена като [Big-theta] ⊝ (n 2 )
3) Космическа сложност
Сложността на пространството измерва количеството допълнително пространство, което е необходимо за сортиране на списъка. Сортирането на балончета изисква само едно (1) допълнително пространство за временната променлива, използвана за размяна на стойности. Следователно той има космическа сложност на O (1).
Обобщение
- Алгоритъмът за сортиране на балончета работи, като сравнява две съседни стойности и ги разменя, ако стойността вляво е по-малка от стойността вдясно.
- Внедряването на алгоритъм за сортиране на балончета е относително директно с Python. Всичко, което трябва да използвате, са за цикли и ако инструкции.
- Проблемът, който алгоритъмът за сортиране на балончета решава, е вземането на произволен списък с елементи и превръщането му в подреден списък.
- Алгоритъмът за сортиране на балончета в структурата на данните се представя най-добре, когато списъкът вече е сортиран, тъй като изпълнява минимален брой итерации.
- Алгоритъмът за сортиране на балончета не се представя добре, когато списъкът е в обратен ред.
- Сортирането на мехурчета има времева сложност на O (n 2 ) и пространствена сложност на O (1)
- Алгоритъмът за сортиране на балончета е най-подходящ за академични цели, а не за реални приложения.
- Оптимизираното сортиране на балончета прави алгоритъма по-ефективен, като пропуска ненужни итерации при проверка на вече сортирани стойности.