Bubble Sort — це простий алгоритм сортування, який багаторазово проходить список, порівнює сусідні елементи та міняє їх місцями, якщо вони розташовані в неправильному порядку. Його назва «Bubble Sort», оскільки менші елементи «булькають» у верхній частині списку. Хоча це не найефективніший алгоритм сортування, його легко зрозуміти та реалізувати, що робить його хорошою відправною точкою для вивчення алгоритмів сортування. У цій статті ми розглянемо концепцію бульбашкового сортування, надамо реалізацію Python із виведенням і обговоримо часову складність алгоритму.
Розуміння бульбашкового сортування
Основна ідея Bubble Sort полягає в тому, щоб кілька разів переглядати список, порівнюючи суміжні елементи та міняючи їх місцями, якщо вони не в порядку. Процес триває, доки більше не буде потрібно замінювати, що означає, що список уже відсортовано. Алгоритм отримав свою назву завдяки тому, як дрібніші елементи поступово переміщуються до верхньої частини списку, подібно до того, як бульбашки піднімаються на поверхню.
Давайте розберемо кроки алгоритму Bubble Sort:
- Ітерація по списку: починайте з початку списку та порівнюйте кожну пару суміжних елементів.
- Порівняйте та поміняйте місцями: якщо елементи розташовані в неправильному порядку, поміняйте їх місцями. Це гарантує, що більший елемент «булькає», а менший рухається вниз.
- Продовжуйте повторювати: повторюйте процес для кожної пари суміжних елементів, доки не досягнете кінця списку.
- Повторюйте, доки не буде відсортовано: Продовжуйте переглядати список, доки більше не знадобляться заміни. На цьому етапі список відсортовано.
Хоча Bubble Sort простий для розуміння, це не найефективніший алгоритм сортування, особливо для великих наборів даних. Його часова складність становить O(n^2) у найгіршому випадку, де 'n' — це кількість елементів у списку. Ця квадратична часова складність робить його менш придатним для великих наборів даних у порівнянні з більш просунутими алгоритмами сортування.
Реалізація Bubble Sort у Python
Тепер давайте запровадимо Bubble Sort у Python і поспостерігаємо за його поведінкою за зразком списку:
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)
У цій реалізації функція bubble_sort приймає список (arr) як параметр і сортує його на місці. Вкладений цикл порівнює сусідні елементи та міняє їх місцями, якщо вони розташовані в неправильному порядку. Зовнішній цикл забезпечує повторення процесу, доки не буде відсортовано весь список.
рядок n java
Висновок і пояснення
Давайте запустимо наданий код Python зі списком зразків і подивимося на результат:
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] успішно відсортовано за допомогою алгоритму Bubble Sort, у результаті чого виходить відсортований список [11, 12, 22, 25, 34, 64, 90].
Алгоритм повторює список кілька разів, порівнюючи та міняючи елементи, доки весь список не буде відсортовано. Під час кожного проходу найбільший несортований елемент «булькає» у правильне положення. Цей процес триває до тих пір, поки більше не буде потрібно замінювати, що означає, що список повністю відсортовано.
Хоча Bubble Sort успішно сортує список, важливо зазначити, що його часова складність робить його менш ефективним для великих наборів даних порівняно з іншими алгоритмами сортування, такими як сортування злиттям або швидке сортування.
Часова складність бульбашкового сортування
Розуміння складності алгоритму в часі має вирішальне значення для оцінки його ефективності, особливо при роботі з великими наборами даних. Часова складність бульбашкового сортування становить O(n^2) у найгіршому випадку, де «n» — це кількість елементів у списку.
Давайте розберемо аналіз часової складності:
- Зовнішній цикл виконується для 'n' ітерацій, де 'n' — це кількість елементів у списку.
- Внутрішній цикл також виконується для «n» ітерацій у гіршому випадку. Однак у міру просування алгоритму кількість ітерацій у внутрішньому циклі зменшується, оскільки найбільший несортований елемент розміщується в правильному місці під час кожного проходу.
- У гіршому випадку кількість порівнянь і замін пропорційна квадрату кількості елементів у списку, що призводить до складності O(n^2). Це робить бульбашкове сортування неефективним для великих наборів даних, і в реальних програмах часто віддають перевагу вдосконаленим алгоритмам сортування з кращою складністю часу.
Висновок
У цій статті ми досліджували концепцію бульбашкового сортування, простого алгоритму сортування, який багаторазово порівнює та міняє сусідні елементи, доки не буде відсортовано весь список. Ми надали реалізацію Bubble Sort на Python, запустили її зі списком зразків і проаналізували результат. Крім того, ми обговорили часову складність бульбашкового сортування, підкресливши її найгіршу часову складність O(n^2) і її вплив на ефективність.