[알고리즘] 버블 정렬(bubble sort) 알아보기

안녕하세요🌟

이번 포스팅은 알고리즘 중 [정렬 알고리즘]에 대해서 정리하려고 합니다. 

정렬 알고리즘은 원소(데이터)들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다. 예를 들어서 배열 안에 [ 3, 5, 1, 2, 4 ] 처럼 값이 무작위로 있을 때, 다양한 방법을 통해서 [ 1, 2, 3, 4, 5 ] 와 같이 수 들을 정렬하는 것입니다. 

정렬을 위한 알고리즘은 다양하게 존재합니다. 대표적으로는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 있는데요. 어떤 알고리즘을 사용하느냐에 따라 공간 및 시간 복잡도가 상이하여 서로 다른 수행 시간을 보입니다.

* 다양한 정렬 알고리즘

1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 병합 정렬
5. 퀵 정렬
6. 힙 정렬

---

---

버블 정렬(Bubble sort)

---

• 인접한 두 개의 원소를 비교하여 정렬 방식(어센딩, 디센딩)에 따라 자리를 교체하며 정리하는 방식입니다.
• 이렇게 자리를 교환하면서, 맨 마지막 자리로 이동하는 모습이 물 위로 올라오는 모양과 같다고 하여 버블(Bubble) 정렬이라고 합니다.

어센딩(Ascending) : 오름차순 [ 1, 2, 3, 4, ... , 10 ]
디센딩(Descending) : 내림차순 [ 10, 9, 8, ... , 1 ]

보통 어센딩 방식을 디폴트로 합니다.

 

01. 그림으로 방식 이해하기

어센딩 방식을 예시로 들었습니다.

1) [ 3, 1, 6, 5, 2 ] 를 가진 배열이 있습니다.

 

2) 가장 먼저 index 0 번의 값과 다음 index와 비교를 합니다.

이때 index 0 번의 값이 다음 index의 값보다 크기 때문에 서로 자리를 교체합니다. 그럼 아래와 같이 됩니다.

 

3) 다음은 index 1 번과 다음 index를 비교합니다.

이번에는 index 1 번의 데이터가 다음 index의 값보다 작기 때문에 자리를 교체하지 않습니다.

 

 

4) 위에서 진행한 방법처럼 배열의 끝까지 비교를 진행하면서, 조건에 해당할 때 자리를 교체합니다.

그렇게 모두 비교를 진행하면 위 그림과 같은 상태가 됩니다. 하지만 아직 정렬이 된 상태는 아닙니다.

따라서 다시 처음으로 돌아와 방금처럼 다시 순회를 진행합니다.

 

5) 처음으로 돌아와서 index 0번과 index 1번부터 비교를 시작합니다.

여기서 1 , 3 , 5 는 조건에 맞게 정렬된 상태이기 때문에 변화는 없습니다. 따라서 이 부분은 생략하도록 하겠습니다.

 

6) 다음은 index 2번의 5와 다음 index의 2와 비교를 합니다.

index 2번의 5가 다음 index의 값보다 크기 때문에 자리를 교체합니다. 그럼 아래 그림과 같이 됩니다.

이후 5와 6은 비교를 하지 않습니다. 이는 버블 정렬의 특징으로 순회를 할 때마다 가장 큰 수가 제일 뒤로 가서 고정이 되는 방식입니다. 즉, 다음 순회 시 비교 대상에서 제외되는 것입니다.

이제 아까와 동일하게 앞으로 돌아와서 다시 순회를 진행합니다.

이번에도 역시 5, 6은 고정이기 때문에 1, 3, 2만 비교를 진행하면 됩니다.

 

 

7) 3이 2보다 크기 때문에 자리를 교체합니다.

이제 3도 고정되었습니다. 다시 처음으로 돌아가서 똑같이 반복합니다.

마지막으로 index 0번과 다음 index를 비교했을 때, index 0이 작기 때문에 자리를 교체하지 않아도 됩니다.

이제 정렬이 모두 된 것을 알 수 있습니다.

---

02. 코드 구현

참고 클래스 : Collections.swap
-> Java.util 의 클래스
-> Collections.swap(List<?> list, int i, int j);
-> list의 index i와 index j 의 자리를 바꿈.

참고 클래스 : Math.random
-> Java.lang 의 클래스
-> Math.random()
-> 0 이상 1 미만의 부동 소수점 값을 가져올 수 있음 => 0.12

1) 정렬 메서드 구현

import java.util.ArrayList;
import java.util.Collections;

public class MyBubbleSort {

	public ArrayList<Integer> sort(ArrayList<Integer> array) {
    	
        for(int i = 0; i < array.size()-1; i++) { //outter for문
        	
            // 교체가 되었는지 체크할 변수
            boolean swap = false;
            
            // 순회를 한번 끝내 때마다 제일 큰 수를 찾고 고정시키기 때문에
            // 조건에서 array.size() -1 에 -i 를 붙인다.
            for(int j = 0; i < array.size()-1-i; i++) { // inner for문
            
            	if(array.get(j) > array.get(j + 1)) {
                
                	// java.utill 의 Collections.swap을 활용해서 자리 교체
                    Collections.swap(array, j, j+1);
                    swap = true; // 교체가 되었기 때문에 true 가 된다.
                }
             
           }
           
           // swap이 false이면 정렬이 다 되었다는 뜻으로 더 순회하지않고 for문을 종료
           if(swap == false) {
           	   break;
           }
        }
        
        return array; // 정렬된 배열을 반환
	}
}

outter for문에서 i < array.size() -1 조건이 있습니다.
여기서 -1 이 붙는 이유는 모든 순회를 마치고 값이 1개만 남았을 때는 비교를 할 필요가 없기 때문입니다.

inner for 문에서는 array.size()에 -1 과 -i 가 붙어있는데요.
마지막 index는 이미 전에 비교를 했기 때문에 -1을 붙여주어 마지막 index는 비교를 하지 않습니다.
그리고 -i 는 inner for문이 종료할 때마다 제일 끝에 최대 값이 이미 결정되기 때문에 -i를 작성하여 점점 비교 수를 줄이는 것입니다.

 

2) 실행

    public static void main(String[] args) {

        ArrayList<Integer> array = new ArrayList<>();

        array.add(3);
        array.add(1);
        array.add(6);
        array.add(5);
        array.add(2);

		// array = [3, 1, 6, 5, 2]
        
        MyBubbleSort bsTest = new MyBubbleSort();

        System.out.println(bsTest.sort(array)); // [1,2,3,5,6]

    }

---

03. 시간 복잡도

버블 정렬은 코드를 보다시피 for 문을 두 번 사용하면서 O(n^2) 시간 복잡도가 발생합니다.

위에서 작성한 코드를 통해서 조금 더 자세하게 보도록 하겠습니다.

데이터가 5개 있을 때 4번 순회를 진행했습니다. 그리고 각 순회마다 비교를 진행했는데요.

• 1번 순회 때 4번 비교
• 2번 순회 때 3번 비교
• 3번 순회 때 2번 비교
• 4번 순회 때 1번 비교

4 + 3 + 2 + 1을 하여 총 10번을 비교한 것을 알 수 있습니다.

이를 일반화하면, (N-1) + (N-2) + (N-3) + ... + 1 이와 같이 되고, 이것은 등차수열의 합이란 것을 알 수 있습니다.

따라서 N개의 데이터를 등차수열 공식으로 나타내면 N ( N -1) / 2 가 되면서,

최고차항만 나타내면서 계수를 제외하는 빅오 표기법에 따라 시간 복잡도는 O(n^2)가 됩니다.