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

인접한 2개의 레코드를 비교하여 크기가 순서대로 있지 않으면 서로 교환하는 알고리즘

 

[1,2,3,4,5] 1~5까지의 데이터 를 비교 

4번 비교 1-2, 2-3, 3-4, 4-5 => 1회전 가장 큰수가 결정됨

1회전 (n-1)=4번 비교

2회전 (n-2)=3번 비교

3회전 (n-3)=2번 비교

4회전 (n-4)=1번 비교

5회전 자동으로 정렬끝

n회전이 끝나고 버블정렬이 완료됨

 

Bubble Sort의 시간 복잡도 => 데이터의 개수가 적을 때 이용!

best case O(n2)

worst case O(n2)

평균적인 시간복잡도 O(n2)

 

---

 

data=[3,2,5,4,1]

 

def bubbleSort1(data):

  for i in range(len(data)-1,-1,-1):

    for j in range(i):

      if data[j] > data[j+1]:

        data[j],data[j+1]=data[j+1],data[j] #리스트 스왑

  print(data)

 

bubbleSort1(data)

 

---

data=[3,2,5,4,1]

 

def swap(x, i, j):

    x[i], x[j] = x[j], x[i]

 

def bubbleSort2(x):

    for size in reversed(range(len(x))):

        for i in range(size):

            if x[i] > x[i+1]:

                swap(x, i, i+1)

    print(data)

 

bubbleSort2(data)

---

 

참고

Study Note - 파이썬으로 정렬 알고리즘 구현하기