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

본 포스트는 개인 스터디에 대한 정리 및 기록의 용도로써, 오개념이 존재 할 수 있습니다. 글은 상시 수정되며, 지적사항에 대해서 검토 후 수정하겠습니다.

---

 

버블정렬

아마 가장 쉬운 정렬 알고리즘이지 않을까 싶다. 다른 정렬알고리즘을 몰랐을때 또는 자바나 C++의 내장 sort() 알고리즘의 사용법을 몰랐을때는 정렬해야하는 상황이 오면 함수로 만들어두고 사용했었다. 그러나 자료구조를 배우면서 시간복잡도를 배우게 됐는데, 상당히 비효율적인 알고리즘이었다. 처음 코딩을 배울때는 딱히 효율성을 생각하지 않아도 되기 때문에 사용했지만 요즘은 사용하지 않는다. 그러나 이 알고리즘을 사용하면서 for문에 대한 이해도가 생겼던 기억이 있다.

 

 

 

버블정렬의 속도

먼저 시작에 앞서 왜 비효율적이라고 했는지 버블정렬과 퀵소트 알고리즘을 비교해 보면 보면 알 수있다. 모든 두수를 하나하나 다 비교하고, 또 다음 루프에서도 하나하나 다 비교한다. 그리고 또 다음 루프에서도 하나하나 다 비교한다. 또 다 본다. 그래서인지 정겹다...

 

버블정렬

다음에 다뤄볼 퀵소트는 버블정렬과 다르게 많이 빠른걸 볼 수 있다. 이게 양이 많아지면 많아질 수록 꽤 많은 시간 차가 나기 때문에, 괜히 버블정렬을 써서 이상한곳에서 시간을 낭비 하지 않았으면 한다.

퀵정렬

 

 

버블정렬 시간복잡도

최선의 조건, 최악의 조건 모두 N^2 이다. 어떤 경우에도 상관 없이 모든걸 비교해보기 때문이다.

O(n^2)

 

 

---

코드

public class BubbleSort {
    static final int n = 10;
    static int[] arr = {2,7,10,3,8,4,5,6,1,9};

    public static void main(String[] args) {
        int temp;
        for(int i=n; i>0; i--){
            for(int j=0; j<i-1; j++){
                if(arr[j] > arr[j+1]){
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        
	//출력
        for(int i=0; i<n; i++){
            System.out.print(arr[i] + " ");
        }
    }

 

코드는 매우 단순하다.  밖(i)의 포문이 한번 돌면 배열내의 가장큰 수가 맨 오른쪽으로 이동한다. 안(j) 포문은 맨 오른쪽으로 보낸 가장큰 수는 제외하고 그 전까지 반복하는데, 이때 현재 index와 index+1의 수를 비교하고 크면 오른쪽으로 보낸다.

자료 만드는게 은근 오래걸린다. 방법을 찾아봐야겠다.

---

 

처음 배울때는 머리 아팠는데, 막상 정리해보니까 뭐를 설명해야하는지도 잘 모르겠다. 여튼 나는 버블정렬을 사용할때, 가장 큰 수는 맨 오른쪽으로 보내버린다는 생각으로 쓴다. 그래서 밖의 포문도 (i=0 ~~ i <n) 이 아니라 (i = n ~~ i > 0)으로 쓴다. 나는 이래야 뭔가 논리적으로 맞는거 같다.

---

 

Sorting Algorithms Animations