Буббле Сорт је једноставан алгоритам за сортирање који више пута корача кроз листу, упоређује суседне елементе и мења их ако су у погрешном редоследу. Назива се 'Буббле Сорт' јер мањи елементи 'мехурићи' на врху листе. Иако није најефикаснији алгоритам за сортирање, лак је за разумевање и имплементацију, што га чини добром полазном тачком за учење о алгоритмима за сортирање. У овом чланку ћемо се позабавити концептом Буббле Сортирања, пружити Питхон имплементацију са излазом и дискутовати о временској сложености алгоритма.
Разумевање сортирања мехурића
Основна идеја која стоји иза Буббле Сорт је да се листа понавља више пута, упоређујући суседне елементе и замењујући их ако нису у реду. Процес се наставља све док више не буду потребне замене, што указује да је листа сада сортирана. Алгоритам је добио име по начину на који се мањи елементи постепено померају на врх листе, слично као мехурићи који се дижу на површину.
Хајде да разложимо кораке алгоритма за сортирање мехурића:
- Итерирајте кроз листу: Почните од почетка листе и упоредите сваки пар суседних елемената.
- Упоредите и замените: Ако су елементи у погрешном редоследу, замените их. Ово осигурава да се већи елемент 'подиже', а мањи помера надоле.
- Наставите са понављањем: Поновите процес за сваки пар суседних елемената док се не дође до краја листе.
- Понављајте док се не сортирате: Наставите да се понављате кроз листу све док више не буду потребне замене. У овом тренутку, листа је сортирана.
Иако је сортирање мехурићем једноставно за разумевање, то није најефикаснији алгоритам за сортирање, посебно за велике скупове података. Његова временска сложеност је О(н^2) у најгорем случају, где је 'н' број елемената на листи. Ова квадратна временска сложеност чини га мање погодним за велике скупове података у поређењу са напреднијим алгоритмима за сортирање.
Питхон имплементација Буббле Сорт
Сада, хајде да имплементирамо Буббле Сорт у Питхон-у и посматрамо његово понашање помоћу листе узорака:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
У овој имплементацији, буббле_сорт функција узима листу (арр) као свој параметар и сортира је на месту. Угнежђена петља упоређује суседне елементе и мења их ако су у погрешном редоследу. Спољна петља обезбеђује да се процес понавља док се цела листа не сортира.
Излаз и објашњење
Хајде да покренемо обезбеђени Питхон код са листом узорака и посматрамо излаз:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Овде је оригинална листа [64, 34, 25, 12, 22, 11, 90] успешно сортирана коришћењем алгоритма Буббле Сорт, што резултира сортираном листом [11, 12, 22, 25, 34, 64, 90].
Алгоритам се понавља кроз листу више пута, упоређујући и мењајући елементе док се цела листа не сортира. У сваком пролазу, највећи несортирани елемент 'мехуриће' до свог исправног положаја. Овај процес се наставља све док више не буду потребне замене, што указује да је листа у потпуности сортирана.
Док Буббле Сорт успешно сортира листу, важно је напоменути да је због временске сложености мање ефикасан за велике скупове података у поређењу са другим алгоритмима за сортирање као што су сортирање спајањем или брзо сортирање.
Временска сложеност сортирања мехурића
Разумевање временске сложености алгоритма је кључно за процену његове ефикасности, посебно када се ради о великим скуповима података. Временска сложеност Буббле Сортирања је О(н^2) у најгорем случају, где је 'н' број елемената на листи.
Хајде да разложимо анализу временске сложености:
- Спољна петља се покреће за 'н' итерације, где је 'н' број елемената на листи.
- Унутрашња петља такође ради за 'н' итерације у најгорем случају. Међутим, како алгоритам напредује, број итерација у унутрашњој петљи се смањује, пошто се највећи несортирани елемент поставља на своју тачну позицију у сваком пролазу.
- У најгорем случају, број поређења и замена је пропорционалан квадрату броја елемената на листи, што резултира О(н^2) временском сложеношћу. Ово чини Буббле Сорт неефикасним за велике скупове података, а напреднији алгоритми за сортирање са бољом временском сложеношћу се често преферирају у апликацијама из стварног света.
Закључак
У овом чланку смо истражили концепт Буббле Сорт, једноставног алгоритма за сортирање који више пута упоређује и мења суседне елементе док се цела листа не сортира. Обезбедили смо Питхон имплементацију Буббле Сорт, покренули је са листом узорака и анализирали излаз. Поред тога, разговарали смо о временској сложености Буббле Сорт-а, наглашавајући његову О(н^2) најгорем случају временске сложености и његове импликације на ефикасност.