[Algorithm] Bubble Sort(버블 정렬)

Introduce

• 본 코드는 Python으로 짜져있습니다.
• 기준은 오름차순을 기준으로 하고 있습니다.
• 우측상단의 흰색배경에서 보는 것을 추천드립니다.

개념

• 가장 마지막 Index에서부터 비교
• 인접한 Index가 value가 크면 교환
• Index가 0이 될 때까지 실행 뒤, 마지막에서 두 번째 Index에서 반복
• 아래 그림처럼 오른쪽에서 왼쪽으로 가도 되고, 왼쪽에서 오른쪽으로 가도 상관 없음
  

Code

• 구현 1

lst = [92, 88, 12, 76, 14, 79, 5, 72, 3]
# 거품 정렬
def bubble(lst):
    for i in range(len(lst)):
        for j in range(len(lst)-1):
            if lst[j] > lst[j+1]:  # 오른쪽 value보다 크면 교환
                tmp = lst[j]
                lst[j] = lst[j+1]
                lst[j+1] = tmp
                
        print(i+1,"회차")
        print(lst)

bubble(lst)

• 구현 2
  • swap 사용

lst = [92, 88, 12, 76, 14, 79, 5, 72, 3]
# 거품 정렬
def bubble_sort(lst):
    for i in range(len(lst)-1, 0, -1):          # 뒤에서 부터 정렬한다.
        for j in range(len(i)):                 # 앞에서 부터 조회
            if lst[j] > lst[j+1]:               # 인근 값 대소비교
                lst[j], lst[j+1] = lst[j+1], lst[j]
                
    print(i+1,"회차")
    print(lst)
        
bubble_sort(lst)

결과

• 장점

  • 구현이 매우 간단

• 단점

  • 순서에 맞지 않은 요소를 인접한 요소와 교환
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어남

• 정렬 알고리즘 시간복잡도