이 글은 나동빈님의 "이것이 코딩테스트다 with 파이썬"책과 유튜브 강의를
교재로 삼아 공부한 후 나의 이해한 내용을 정리한 글입니다

버블 정렬

핵심 아이디어

옆에 있는 값과 비교하여 더 큰 값을 뒤로 보낸다

정렬 진행 방식

1 ) 정렬할 배열을 탐색하며 현재 탐색하는 값과 그 값의 오른쪽에 있는 값을 비교한다.
2 ) 비교 한 후 더 작은 값을 앞 (왼쪽)으로 보낸다
3 ) 정렬할 배열을 모두 탐색 할 때 까지 1), 2)의 과정을 반복하여 시행한다.
4 ) 정렬 완료

기본 코드 구조

def f_bubble(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-(i+1)):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

코드 설명

버블 정렬은 현재 탐색하는 기준요소의 옆의 값과 비교하여 더 큰 값을 오른쪽으로 보내는 방식의 알고리즘이다

즉 현재 탐색하는 요소가 바뀔 때마다 요소끼리의 자리 바꿈을 실시 한다.
그 결과, 정렬이 완료된 요소는 배열의 맨 오른쪽에 위치하게 된다.

코드 1

def f_bubble(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-(i+1)):

우선 버블정렬도 선택 정렬과 동일하게 for문을 이용하여 배열 안 요소를 탐색한다.

하지만 버블 정렬은 선택 정렬과 달리 현재 요소를 기준으로 바로 옆에 있는 값을 그때그때 비교하여 자리를 바꾸기 때문에 기준값이 따로 필요하지 않다

위에서 언급 했듯이 버블 정렬은 정렬이 완료된 요소는 배열의 마지막에 위치하게 된다.
따라서 정렬이 완료된 요소는 탐색할 필요가 없으므로 두 번째 for문의 범위를 0, len(arr) - (i+1)로 설정하여 탐색을 실시한다.

• 여기서 현재 요소, 요소의 오른쪽을 비교 하므로 len(arr) - 1의 범위를 가져야 하나, i가 0,1,2 ... 를 탐색하며 바뀔때마다 배열의 마지막 부분은 i개의 정렬이 완료된 요소가 위치하게 된다.
  이 요소들은 탐색하지 않아도 되는 범위이기에 len(arr) - ( i + 1 )의 범위를 설정한다.

코드 2
if arr[j] > arr[j+1]:
   temp = arr[j]
   arr[j] = arr[j+1]
   arr[j+1] = temp

두 번째 for문안에는 현재 탐색 요소 j와 j+1을 비교하여 자리를 바꾸는 조건문이 삽입 된다.
만약 배열의 인덱스 j의 요소값이 인덱스 j+1의 요소 값보다 크다면 자리를 바꾼다.
선택정렬에서 사용한 temp 변수를 선언,할당하여 j와 j+1의 자리를 바꿔준다.

위에서 말했듯이 선택 정렬과 달리 버블 정렬은 요소 하나하나를 탐색 할 때마다 대소를 비교하여 자리를 바꿔준다.

두번째 for문을 종료하면, 다음 i의 값을 탐색하여 다시 두 번째 for문의 과정을 실행하며 정렬을 실시한다.
위 과정을 첫번째 for문이 종료 될 때까지 반복하면 최종적으로 버블 정렬이 완료된다.

최종 코드 // 입 출력 값

arr = [16, 7, 12, 11, 8, 10, 9, 15, 13, 14]

def f_bubble(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-(i+1)):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr
    
print(f_bubble(arr))
 
==> [7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

버블 정렬을 공부 해보니 확실히 알고리즘 자체가 직관적이고 간단 하다 보니 평소에 사용하기가 매우 편리 했다.
물론 퀵 정렬, 병합 정렬 보다는 시간 복잡도가 큰 편이긴 하지만 라이트한 데이터를 다루기에는 괜찮은 알고리즘이라는 생각이 들었다.