[Sort] 버블 정렬 (Bubble Sort)

소개

• 탐색의 효율적인 방법중 하나가 정렬이다.
• 정렬한 뒤 탐색을 하면 탐색의 효율성이 높아진다.
• 정렬 알고리즘 중 하나가 버블 정렬이다.

 

특징

• 버블 정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬이다.
• 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생 될 수 있다.

 

동작원리

• 리스트 안에 들어있는 두 개의 인접한 수를 비교
• 만약 순서에 맞지 않는다면 교환

 

예시

배열 [5, 1, 6, 2, 4, 3] 이 있다고 가정

1. 5와 1을 비교, 1이 5보다 작기 때문에 교환이 됨
2. 5와 6을 비교, 5가 6보다 작기 때문에 그 다음 요소로 넘어감
3. 6과 2를 비교. 2가 6보다 작기 때문에 교환이 됨
4. 6과 3 비교, 3이 6보다 작기 때문에 교환

위의 단계별로 배열결과를 써보자.

1. [5, 1, 6, 2, 4, 3]
2. [1, 5, 6, 2, 4, 3]
3. [1, 5, 6, 2, 4, 3]
4. [1, 5, 2, 6, 4, 3]
5. [1, 5, 2, 4, 6, 3]
6. [1, 5, 2, 4, 3, 6]

수행 한번만에 정렬된 리스트가 나오는 것을 보장하지 않는다.

즉 n개의 요소를 정렬하기 위해 n-1 번 실행해야한다.

n(n-1) = n2- n

시간복잡도 O(n2) 으로 계산

for (int j = 0; j < arr.length; j++) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}