[알고리즘/정렬 알고리즘] 버블 정렬 (Bubble sort) Java, Python

버블 정렬(Bubble sort) 알고리즘의 개념

• 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 알고리즘이다.
• 선택 정렬과 기본 개념이 비슷하다.

버블 정렬(Bubble sort) 예제

• 배열에 1, 5, 4, 10, 8, 19, 3 순으로 값이 들어가 있고 오름차순으로 정렬할 때의 버블 정렬 예를 확인해보자
• 버블 정렬은 이웃한 두 요소 간 대소 관계를 파악하여 정렬하는 행위를 배열 전체에 한번 해주게 된다.  다음 두 요소 간 대소 관계 파악은 이전에 했던 대소 관계 비교 횟수보다 -1 만큼만 해줘도 된다는 특징이 있다.

1회전

• 위와 같이 오른쪽 끝에서 왼쪽 끝까지 이웃한 숫자끼리 대소 비교를 하며 정렬했다.
• 중요한 포인트는 이렇게 1회전이 끝난 버블 정렬의 맨 왼쪽 요소는 배열 중 최솟값으로 정렬 된다는 것이다. 그렇다면 우리는 다음 2회전 시 맨 왼쪽 요소를 제외하고 정렬을 하면 되고, 3, 4회전도 마찬가지로 적용할 수 있다.

2회전 시작 초반부분

• 이렇게 2회전 때는 1까지 비교하지 않고 1은 그대로 둔 채 다시 대소 비교를 한다.

 

[Java 코드]

public class BubbleSort {
    
    public static void main(String args[]) {
        int[] arr = {1, 5, 4, 10, 8, 19, 3};
        int temp = 0;
        int N = arr.length;
        
        for(int i = 0; i < N-1; i++) {
            for(int j = N-1; j > i; j--) {
                if(arr[j-1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        
        for(int a : arr) {
            System.out.print(a +" ");
        }
        
    }
}
 

 

 

[Python 코드]

def BubbleSort(arr):
    temp = 0
    N = len(arr)
 
    for i in range(N-1):
        for j in range(N-1, i, -1):
            if arr[j-1] > arr[j]:
                temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
 
    print(arr)
 
 
arr = [1, 5, 4, 10, 8, 19, 3]
BubbleSort(arr)