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

버블 정렬 알고리즘?

서로 인접한 두 원소를 비교하여 오름차순 혹은 내림 차선으로 정렬한다.

1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

특징

장점

• 구현이 단순하다.

단점

• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 다른 모든 요소들과 교환되어야 한다.
• 즉 성능이 좋지않다.
• 때문에 거의 쓰이지 않는다.

 

구현

public static void bubbleSort( int[] target ){
    for( int i = target.length - 1; i > 0; i -- ){
        for( int j = 0; j < i; j++ ){
            if( target[j] > target[j + 1] ){
                int temp = target[j];
                target[j] = target[j + 1];
                target[j + 1] = temp;
            }
        }
    }
}

 

시간 복잡도

최상, 평균, 최악 모두 O(n^2)

 

---

참고 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog