Bubble Sort

• 개념 : 서로 인접한 두 원소를 비교해 교환하며 정렬하는 알고리즘.
• 특징
  • 1회전 후에는 가장 큰 원소가 맨 뒤로 이동
  • Stable sort
  • swap이 move보다 더 복잡해 쓰이지 않음.
  • 비효율적
• 장점
  • 간단한 구현 ( 간단한 데이터 정렬에는 사용되기도 함.)
• 단점
  • 순서 안맞는 요소를 인접요소와 교환
  • 가장 왼쪽에서 가장 오른쪽으로 이동하려면 모든 요소들과 교환되야함.
  • 최종 위치에 이미 있는 경우에도 교환되는 일 발생 → 불필요한 연산
• 시간 복잡도 : $O(n^2)$ (최선, 평균, 최악 모두 동일)
• 공간복잡도 : $O(1)$ (주어진 배열안에서 교환으로 정렬하는 제자리 정렬)
• 🔨 개선 🔨
  • 특정 회차에서 정렬이 완료됐음에도 마지막 회차까지 비교 연산 불필요하게 진행함.
  • 중간 회차에서 데이터 swap이 진행되지 않으면 정렬 완료된 것이므로 연산 종료

a = [6,5,3,1,8,7,2,4]
    
    # Solution 1
    for i in range(len(a)-1, 0, -1):
        flag = False
        for j in range(i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                flag = True
        if not flag:
            break
    #    print(a)
    
    # Result #
    #[5, 3, 1, 6, 7, 2, 4, 8]
    #[3, 1, 5, 6, 2, 4, 7, 8]
    #[1, 3, 5, 2, 4, 6, 7, 8]
    #[1, 3, 2, 4, 5, 6, 7, 8]
    #[1, 2, 3, 4, 5, 6, 7, 8]
    
    # Solution 2
    end = len(a) -1
    while end > 0:
        last = 0
        for i in range(end):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                last = i
        end = last
    #    print(a)
    
    # Result #
    #[5, 3, 1, 6, 7, 2, 4, 8]
    #[3, 1, 5, 6, 2, 4, 7, 8]
    #[1, 3, 5, 2, 4, 6, 7, 8]
    #[1, 3, 2, 4, 5, 6, 7, 8]
    #[1, 2, 3, 4, 5, 6, 7, 8]
    #[1, 2, 3, 4, 5, 6, 7, 8]