[알고리즘][정렬] 버블 정렬 - Bubble Sort

728x90

 

 

 

🙆‍♂️버블 정렬

---

서로 인접한 두 원소의 대소를 비교해서 조건에 따라 교환을 수행하여 정렬하는 방법입니다.

직관적인 정렬 방식입니다.

 

🙋‍♂️방식

---

a=[7,3,1,6,2]

이렇게 배열이 있을 때 버블 정렬을 사용해서 오름차순 정렬을 한다고 했을 때

a[0]과 a[1]을 비교해서 a[0]의 크기가 작다면 가만히 있고 크다면 a[1]과 자리를 바꿔줍니다.

 

#1단계의 첫 번째 스위칭
a=[3,7,1,6,2]

#1단계의 두 번째 스위칭
a=[3,1,7,6,2]

#1단계의 세 번째 스위칭
a=[3,1,6,7,2]

#1단계의 네 번째 스위칭
a=[3,1,6,2,7]

첫 번째 단계를 수행하면 이런식으로 수행되어 가장 큰 수인 7이 뒤로 옮겨지고 

그 다음 계속적으로 수행하면 큰 수 부터 우측에 쌓이게 됩니다.

 

버블 정렬은 이러한 무지성 교환 특성으로 인해서 시간복잡도가 O(n^2)으로 큽니다. 

그러나 안정적인 정렬인 특징이 있어서 2가지 값을 (이름, 나이) 정렬하고자 할 때 잘 수행할 수 있습니다.

 

def bubble(arr):
    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            if arr[i]>arr[j]:
                tmp = arr[i]
                arr[i]=arr[j]
                arr[j]=tmp
    return arr

위의 코드로 버블정렬을 사용할 수 있습니다.