[알고리즘]-[정렬]-버블정렬(JAVA)

버블정렬 (Bubble Sort)

개념

• 인접한 두 원소를 비교하여 큰 수를 뒤로 보내는 알고리즘 이다.
  
• 시간 복잡도는 O(n^2) 의 시간 복잡도를 가지며 정렬 알고리즘 처리속도가 제일 느리다.
• 장점은 코드가 단순해서 구현하기가 편하고 자주 사용된다.
• 단점은 처리속도가 느리다. 처리속도가 느리기 때문에 용량이 큰 리스트를 정렬할 때는 적합하지 않다.

처리과정

위와 같이 길이가 10인 {14, 4, 8, 23, 11, 5, 3, 2, 4, 9} 정수형 배열이 존재하고 이 배열을 버블 정렬로 정렬을 하고자 하면

0번째 인덱스에서 배열의 길이만큼 반복문을 돌면서 (i) 와 (i+1) 인덱스의 값을 비교하고

( i ) 인덱스의 값이 (i + 1) 인덱스의 값 보다 크다면 ( i ) 인덱스와 ( i + 1 ) 인덱스의 값을 교체한다.

반복문을 돌 때마다 배열의 끝 부터 큰 수부터 작은수로 정렬이 되고 마침내 0 번 인덱스까지 도달하면 버블정렬이 완료된다.

이미 정렬이 된 인덱스는 다음 조회에서는 접근하지 않아도 된다.

소스 (JAVA)

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