파이썬과 컴퓨터 사이언스(알고리즘) - 버블 정렬 (bubble sort)

7. 버블 정렬 (bubble sort)

  • 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
  • 다음 그림과 https://visualgo.net/en/sorting 를 보며 이해

어떻게 코드로 만들까?

  • 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
    • 예: data_list = [1, 9, 3, 2]
      • 1차 로직 적용
        • 1 와 9 비교, 자리바꿈없음 [1, 9, 3, 2]
        • 9 와 3 비교, 자리바꿈 [1, 3, 9, 2]
        • 9 와 2 비교, 자리바꿈 [1, 3, 2, 9]
      • 2차 로직 적용
        • 1 와 3 비교, 자리바꿈없음 [1, 3, 2, 9]
        • 3 과 2 비교, 자리바꿈 [1, 2, 3, 9]
        • 3 와 9 비교, 자리바꿈없음 [1, 2, 3, 9]
      • 3차 로직 적용
        • 1 과 2 비교, 자리바꿈없음 [1, 2, 3, 9]
        • 2 과 3 비교, 자리바꿈없음 [1, 2, 3, 9]
        • 3 과 9 비교, 자리바꿈없음 [1, 2, 3, 9]
프로그래밍 연습
데이터가 두개 일때 동작하는 버블 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
프로그래밍 연습
데이터가 세개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법
프로그래밍 연습
데이터가 네개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 근육을 키우는 방법

알고리즘 생각해보기

  • 특이점 찾아보기
    • n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용한다.
    • 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
    • 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.
  1. for num in range(len(data_list)) 반복
  2. swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
  3. 반복문 안에서, for index in range(len(data_list) - num - 1) n - 1번 반복해야 하므로
  4. 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
  5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
  6. swap += 1
  7. 반복문 안에서, if swap == 0 이면, break 끝
In [ ]:
import random 
data_list = random.sample(range(100), 50)
In [ ]:
def bubble_sort(data):
    for index in range(len(data_list)):
        swap = 0
        for index2 in range(len(data_list) - 1 - index):
            if data_list[index2] > data_list[index2 + 1]:
                data_list[index2], data_list[index2 + 1] = data_list[index2 + 1], data_list[index2]
                swap += 1
        if swap == 0:
            break
    return data_list
In [ ]:
bubble_sort(data_list)

알고리즘 분석

  • 반복문이 두 개 O($n^2$)
    • 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
  • 완전 정렬이 되어 있는 상태라면 최선은 O(n)
프로그래밍 연습
지금 설명한 삽입 정렬을 지금 다시 스스로 작성해보세요
In [ ]:
import random 
data_list = random.sample(range(100), 10)
In [ ]:
def bubble_sort(data_list):
    for index in range(len(data_list) - 1):
        for index2 in range(len(data_list) - index - 1):
            if data_list[index2] > data_list[index2 + 1]:
                data_list[index2], data_list[index2 + 1] = data_list[index2 + 1], data_list[index2]
    return data_list
    
In [ ]:
bubble_sort(data_list)