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

정렬 알고리즘(Sorting Algorithms)

: 데이터를 특정 순서로 정렬하는 알고리즘

버블 정렬(Bubble Sort)

: 가장 직관적이고 단순하지만, 다른 정렬에 비해 단점이 많음.

정렬 알고리즘 중에 젤 안좋은애임. 원래 젤 안좋은 것부터 배운다고 함

 

 

버블 정렬 알고리즘의 과정입미다

 

예시 리스트 [3, 2, 1, 4, 0] 

 

맨 앞(0번째, 1번째)의 두 요소를 비교해서 '앞의 숫자가 더 클 경우' 에는 두 요소의 위치를 변경해준다. (swap)

 

그 다음엔 1번째와 2번째 요소 비교하고, 앞의 숫자가 더 크니까 위치를 변경해줌.

 

다음으로 2번째와 3번째 요소를 비교했는데, 앞의 숫자가 더 작다. 그럼 위치변경이 일어나지 않는다. 그냥 아무일도 안일어나고 다음이 이어서 진행됨.

 

다음 이어서 3번째와 4번째 요소 비교. 앞의 숫자가 크니까 위치 변경해준다.

 

마지막번째 요소까지 비교 끝냈으니 1라운드 순회 끝!

제일 큰 값인 4가 배열의 끝에 정렬되었다.

 

2라운드 시작! 다시 맨 앞부터 두 개씩 비교. 0번째가 1번째 보다 크므로 위치 변경.

 

1번째가 2번째보다 작으므로 위치 변경없이 넘어감.

 

2번째가 3번째보다 크므로 위치 변경.

 

 

3번째 4번째 비교할 차례인데,

4번째자리에는 이미 가장 큰 수(4)가 있다. 1라운드에서 결정됐으니까.

그래서 굳이 중복해서 비교할 필요가 없다.

같은 맥락으로 3라운드에서는 2번째 요소까지만 비교하면 된다.

 

 

버블 정렬 코드 구현하기

• 배열의 길이만큼 라운드 반복 → for
• 매 라운드마다 처음부터 비교 반복 → for
• 배열 마지막 i개의 요소는 비교할 필요 없음 → range( -i )
• 앞의 수가 뒤의 수보다 크다면 실행 → if
• 교환(swap) 하기 → a, b = b, a

def bubble_sort(arr):                   # 버블정렬 함수 선언
    n = len(arr)                        # 변수n = 배열의 길이
    for i in range(n):                  # 외부루프(라운드 반복. 0부터 n-1까지)
        for j in range(n-i-1):          # 내부루프(j+1이 있으니 -1, 마지막 i개 요소 제외하고 반복)
            if arr[j] > arr[j+1]:       # 앞의 값이 다음 값보다 클 경우
                arr[j], arr[j+1] = arr[j+1], arr[j]      # swap 해준다
    return arr                          # 반복이 끝난 배열 반환

array = [3, 2, 1, 4, 0]                 # 예시 배열
print(bubble_sort(array))               # [0, 1, 2, 3, 4]

 

해당 코드는 다음과 같은 과정을 거쳐서 출력된다

외부 루프 1: [3, 2, 1, 4, 0]
  내부 루프 1: [2, 3, 1, 4, 0]
  내부 루프 2: [2, 1, 3, 4, 0]
  내부 루프 3: [2, 1, 3, 4, 0]
  내부 루프 4: [2, 1, 3, 0, 4]
외부 루프 2: [2, 1, 3, 0, 4]
  내부 루프 1: [1, 2, 3, 0, 4]
  내부 루프 2: [1, 2, 3, 0, 4]
  내부 루프 3: [1, 2, 0, 3, 4]
외부 루프 3: [1, 2, 0, 3, 4]
  내부 루프 1: [1, 2, 0, 3, 4]
  내부 루프 2: [1, 0, 2, 3, 4]
외부 루프 4: [1, 0, 2, 3, 4]
  내부 루프 1: [0, 1, 2, 3, 4]
외부 루프 5: [0, 1, 2, 3, 4]

 

라운드가 진행됨에 따라

큰 값들은 점점 배열의 끝으로 이동하고,

작은 값들은 점점 배열의 처음으로 이동한다.

 

이 모습이 거품같아서 버블 정렬임.

 

 

---