버블 정렬은 목록을 오름차순(또는 내림차순)으로 정렬하는 정렬 알고리즘입니다. 이것은 가장 쉬운 정렬 알고리즘이지만 그다지 효율적이지 않습니다. 작은 입력 크기에는 사용할 수 있지만 길이가 더 긴 목록이나 배열에는 시간 효율적이지 않습니다. 시간 복잡도는 O(n^2)입니다. 그러나 이것은 내부 정렬 알고리즘이므로 추가 공간을 사용하지 않습니다. 따라서 공간 복잡도 측면에서 효율적입니다. 그러나 버블정렬보다 더 나은 정렬 알고리즘이 있어 많이 사용되지는 않는다.
버블 정렬은 어떻게 작동합니까?
버블 정렬에서는 두 개의 for 루프가 사용됩니다. 외부 for 루프는 목록을 반복합니다. 내부 for 루프는 또한 모든 외부 루프 반복에 대해 목록을 반복합니다.
버블 정렬의 주요 작업은 두 개의 연속 요소를 비교하는 것입니다. 첫 번째 요소가 다음 요소보다 크면 둘 다 교환하여 더 작은 요소가 앞으로 나오고 더 큰 요소가 뒤로 가도록 합니다. 외부 루프의 한 반복에서 목록의 가장 큰 요소는 마지막 인덱스로 이동합니다. 외부 루프의 두 번째 반복에서 목록의 두 번째로 큰 요소는 두 번째 마지막 인덱스로 이동하는 식입니다. 따라서 모든 반복이 끝날 때 정렬된 목록을 얻습니다.
예시를 통해 더 잘 이해할 수 있습니다.
예
다음 목록을 정렬해야 합니다.
| 5 | 2 | 1 | 3 | 4 |
외부 루프=1
| 5 | 2 | 1 | 3 | 4 |
5>2, 따라서 둘 다 교환
| 2 | 5 | 1 | 3 | 4 |
5>1, 따라서 둘 다 교환
| 2 | 1 | 5 | 3 | 4 |
5>3, 따라서 둘 다 교환
| 2 | 1 | 3 | 5 | 4 |
5>4, 따라서 둘 다 교환
| 2 | 1 | 3 | 5 | 4 |
(가장 큰 요소 5는 첫 번째 외부 반복 후 마지막 인덱스에 도달했습니다)
외부 루프=2
| 2 | 1 | 3 | 5 | 4 |
2>1, 따라서 교환
| 1 | 2 | 3 | 5 | 4 |
교체가 필요하지 않음
| 1 | 2 | 3 | 4 | 5 |
교체가 필요하지 않음
| 1 | 2 | 3 | 4 | 5 |
우리가 볼 수 있듯이 목록은 두 번째 외부 반복 자체에서 정렬됩니다. 그러나 외부 루프는 더 이상의 스왑 작업 없이 3번 더 반복됩니다. 따라서 예제에는 2개의 반복만 표시됩니다. 때때로 목록은 첫 번째 반복 자체에서 정렬될 수 있습니다. 때로는 목록이 마지막 반복에서 정렬될 수 있습니다. 따라서 외부 루프는 항상 n번 반복됩니다.
예시
def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr)-1): if(arr[j]>arr[j+1]): temp=arr[j] arr[j]=arr[j+1] arr[j+1]=temp return arr array=[2,3,1,5,4] print(bubble_sort(array))
출력
[1, 2, 3, 4, 5]