자바 버블정렬

자바 버블정렬

 

버블정렬이란?

이웃한 인덱스중 큰 값을 뒤로 옮기는 방식이다. 인덱스 배열이 15, 11, 1, 3, 8이 있다고 가정하에 버블 정렬을 한다면

정렬은 다음과 같이 바뀐다.

 

 

정렬전 인덱스

15, 11, 1, 3, 8

 

1회전후 : 15가 11보다 크므로 자리바뀜

11, 15, 1, 3, 8

 

2회전후 : 15가 1보다 크므로 자리바뀜

11, 1, 15, 3, 8

 

3회전후 : 15가 3보다 크므로 자리바뀜

11, 1, 3, 15, 8

 

4회전후 : 15가 8보다 크므로 자리바뀜, 15가 가장 큰 수 이므로 이후로 마지막 자리는 비교 안해도됨

11, 1, 3, 8, 15

 

5회전후 : 11이 1보다 크므로 자리바뀜

1, 11, 3, 8, 15

 

6회전후 : 11이 3보다 크므로 자리 바뀜

1, 3, 11, 8, 15

 

7회전후 : 11이 8보다 크므로 자리 바뀜, 11이 두 번째로 큰 수이므로 이후로 4, 5번째 자리는 비교 안함.

1, 3, 8, 11, 15

 

이후 회전 : 정렬된 값이고, 순차적이므로 비교해도 자리 바뀜이 일어나지 않음.

 

 

총비교횟수 : n(n-1)/2

 

시간복잡도(빅오표기법)

최상	평균	최악
O(n^2)	O(n^2)	O(n^2)

 

 

 

 

버블정렬 소스

/*
버블정렬
버블정렬은 이웃하는 인덱스를 비교하여 큰 데이터를 뒤로 보내는 방식이다.
 */
package algorithm;

public class BubbleSort {
    public static void main(String[] args){


        int[] index = {15, 11, 1, 3, 8};        // 정렬되지 않은 인덱스
        int k, tmp;

        System.out.println("시작값");
        System.out.println("15, 11, 1, 3, 8");
        System.out.println("");

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


            for(k = 0; k < index.length; k++){
                System.out.print(index[k]+" ");
            }

            System.out.println("");

        }






    }
}