[알고리즘 개념] 버블정렬 (Bubble Sort)

기본 정렬 알고리즘

버블 정렬 (Bubble Sort)

• 정렬 순서

  1. 주어진 리스트에서 서로 이웃한 데이터를 비교하여 큰 데이터를 뒤로 보낸다

  2. 리스트를 한 바퀴 돌면 가장 큰 값이 가장 뒤로 이동하게 되므로 두 번째 바퀴에는 마지막을 제외하고 1번을 반복한다

• 예시

  순서	리스트	진행 상황
  0	[ 3, 6, 5, 7, 2 ]	초기값
  1	[ 3, 5, 6, 7, 2 ]
  2	[ 3, 5, 6, 2, 7 ]	7 확정
  3	[ 3, 5, 2, 6, 7]	6 확정
  4	[ 3, 2, 5, 6, 7]	5 확정
  5	[ 2, 3, 5, 6, 7]	3 확정
  6	[ 2, 3, 5, 7, 8]	2 확정
  7	[2, 3, 5, 7, 8]	끝

• 코드

def bubble_sort(x):
    length = len(x)

    for i in range(length):
        for j in range(length-i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]

    return x
        

• 시간 복잡도 비교

  기본 정렬 알고리즘	최적	평균	최악
  선택 정렬	N^2	N^2	N^2
  버블 정렬	N^2	N^2	N^2
  삽입 정렬	N	N^2	N^2