버블정렬(Bubble sort) Java 구현

버블정렬(Bubble sort) Java 구현

버블정렬

• 버블정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.

n개의 길이를 가진 배열에서

0번째 값과 1번째 값을 비교하여 자리를 스왑한다.

...

n-2번째 값과 n-1번째값을 비교하여 자리를 스왑한다.

이렇게 첫번째 패스가 이루어지며 다음번엔 배열 n-1개를 가지고 두번째 스텝을 진행한다.

class BubbleSort{
    static void swap(int[] a, int idx1, int idx2){
        int tmp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = tmp;
    } // 인덱스 값을 교환하기 위한 swap 함수 구현

    static void bubbleSort(int[] a, int n){
        for(int i=0; i<n-1;i++){ // 전체 스텝 진행
            for(int j = 0; j<n-1-i;j++){ // 한 스텝
                if(a[j] > a[j+1]){
                    swap(a, j, j+1);
                }
            }
        }
    }
}

시간복잡도 O(n^2)