[알고리즘] 버블 정렬 (Bubble Sort) - JAVA / 자바

버블 정렬(Bubble Sort)

 - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

    ㄴ 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬

    ㄴ 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(Bubble) 정렬이라고 함.

 

 - 수행 과정

정렬되지 않은 배열 L = {69, 30, 16, 22}

69

30

16

22

①	69	30	16	22	②	30	16	22	69
	30	69	16	22		16	30	22	69
	30	16	69	22		16	22	30	69
	30	16	22	69

③	16	22	30	69	④ 버블 정렬 완성	16	22	30	69
	16	22	30	69

 

 - 알고리즘

bubbleSort(list[], n)
    for (i ← n-1; i>0; i ← i-1) {
        for (j ← 0; j<i; j ← j+1) {
            if (list[j] > list[j+1]) then {
                temp ← list[j];
                list[j] ← list[j+1];
                list[j+1] ← temp;
            }
        }
    }
end bubbleSort()

 - 메모리 사용 공간 : n개의 원소에 대해 n개의 메모리 사용

 - 연산 시간

    ㄴ 최선의 경우 : 자료가 이미 정렬되어 있는 경우

        - 비교 횟수 : i번째 원소를 (n-i) 번 비교하므로, n(n-1)/2번

        - 자리 교환 횟수 : 발생 X

    ㄴ 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우

        - 비교 횟수 : i번째 원소를 (n-i) 번 비교하므로, n(n-1)/2번

        - 자리 교환 횟수 : i번째 원소를 (n-i) 번 교환하므로, n(n-1)/2번

 - 평균 시간 복잡도 : O(n^2)

 

< 분류 > 

정렬 장소 - 내부 정렬(Internal Sort)  >  교환 방식

[자료구조] 정렬 (Sort)