기본 정렬 - 버블 정렬 (bubble sort) 알고리즘

1. 버블 정렬(Bubble sort)

: 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째, .... 이런식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

• 서로 인접한 두 우너소를 검사하여 정렬하는 알고리즘이다. - 인접한 두 개의 레코드를 비교하여 순서가 맞지 않으면 서로 교환 하는 방식
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는맨 끝에 있는 자료는 정렬에서 제외, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 증가한다.

2. 예제

- 배열에 1, 6, 4, 5, 3 이 저장되어있다고 가정 -> 오름차순 정렬

 

1회전 :

2회전 :

3회전 :

4회전 :

결과 :

 

3. Java 버블정렬 예제

import java.util.Arrays;

public class bubbleSort {
	public static void main(String[] args) {
	       
        int[] data = { 9, 6, 3, 5, 1 };
       
        for(int i=0;i<data.length-1;i++){
           
            for(int j=0; j< data.length-1-i;j++){
                if(data[j]>data[j+1]){                   
                    int tmp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = tmp;                  
                }              
            }          
            ShowArray(data); //현재 i번째 데이터 출력
        }      
        
        System.out.println("\r\n/////////////bubble sort 결과");
        for(int i = 0; i < data.length; i++){
            System.out.print(data[i]+"  ");
        }
        System.out.println();
 
    }
	
    private static void ShowArray(int[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+"  ");
        }
        System.out.println();
    }
}
 

 

4. 시간 복잡도

데이터의 개수를 n개라고 가정한다면,

(n -1) + (n - 2) + ... + 2 + 1 => n(n - 1)/2이 되므로, O(n^2)만큼의 시간이 걸린다.