정렬 알고리즘 :: 버블소트(Bubble Sort)

버블 소트 Bubble Sort

 

 

 

 

거품이 수면위로 올라오는 모습이라 붙여진 이름이며,

인접한 두 값을 비교하여 크기 순으로 자리를 바꾸고 이를 데이터 열의 끝까지 재차 반복한다.

 

 

정렬되지 않은 데이터 [ 5, 1, 7, 10, 3] 이 있을 때

스왑이 일어날 때마다 표기하여 과정을 살펴보면 다음과 같다.

 

정렬하기 전	5	1	7	10	3
1단계	1	5	7	10	3
2단계	1	5	7	3	10
3단계	1	5	3	7	10
4단계	1	3	5	7	10
정렬 후	1	3	5	7	10

 

첫번째 값이 5와 두번째 값인 1 중 5가 크므로 자리를 바꾼다.

두번째 값 5와 세번째 값 7은 순서가 맞으므로 다음 데이터로 넘어간다.

7과 10도 순서가 맞으므로 다음 데이터로 넘어간다.

10과 3 중 10이 더 크므로 자리를 바꾼다.

 

이러한 버블소트의 장점은 단순함이고 단점은 속도에 있다.

 

CPU가 연산을 처리하기 위해 소요되는 시간을 시간복잡도로 표기하는데 상황에 따라 3가지로 볼 수 있다.

최악의 시나리오로 효율을 계산했을 때는 빅 오(Big-O, O),

최상의 시나리오로 효율을 계산했을 때는 오메가(Omega, ω),

평균적인 시나리오로 효율을 계산했을 때는 세타(Theta, Θ)로 나타낸다.

 

---

~ 광고 타임 ~

---

 

이 가운데 상한을 나타내는 빅 오 표기법을 가장 많이 사용한다.

 

버블 소트는 시간복잡도 O(n^2)에 해당하며, 대표적으로 이중 포문(반복문) 사용시 발생한다.

그래프로 보면 도움될 것 같아서 그려보았다.

 

 

(이미지 캡쳐 : Demos 그래프 계산기)

 

y축을 시간이라고 할 때, 데이터가 늘어날 수록 기하급수적인 증가폭을 보여준다.

 

 

시간복잡도＼데이터 수	16	32	64	128
O(n)	16	32	64	128
O(n^2)	256	1,024	4,096	16,384

 

수치상으로 비교한 표를 보면 보다 체감이 잘 될 것이다.

 

 

---

~ 광고 타임 ~

---

 

 

JAVA 코드

private static void fn_BubbleSort(int[] arr) {
package tisory.blog.it_ing;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		System.out.println(" == 아이티-잉 정렬 알고리즘 == \n");
		int[] arr = {5, 1, 7, 10, 3};
		
		fn_BubbleSort(arr);
		
	}

	private static void fn_BubbleSort(int[] arr) {
		//temp는 스왑용, cnt는 카운트 용이다.
		int temp=0, cnt=0;	//cnt는 생략가능.
		
		System.out.println("#1. 버블소트");
		System.out.println("Input : " + Arrays.toString(arr));
		for(int i=0; i<arr.length; i++){
			for(int j=0; j<arr.length-1; j++){	//보다 효율을 높이려면 반복조건을 arr.length-1-i로 변경하자.
				if(arr[j] > arr[j+1]){    //인접한 두 값을 비교한 후 스왑
					cnt++;
					temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
					System.out.println("STEP" + cnt+ " : " + Arrays.toString(arr));
				}
			}
		}
		System.out.println("Result : " + Arrays.toString(arr));
	}
}

 

 

Syntaxhighlighter 를 사용하느라 시간이 좀 지체됐다.

혹시라도 Syntaxhighlighter로 부등호를 넣고자 할 땐 치환문자를 활용하자.

부등호 < 는 &lt; 로 쓸 수 있고, 부등호 > 는 &gt; 로 쓸 수 있다.

참고로 lt는 less than의 약자, gt는 greater than의 약자다.

 

 

 

 

결과

 

 

 

결과를 출력하면 위와 같다.

 

 

 

 

 

 

C/C++ 코드

 

노트북에 환경설정이 되어있지 않아서 일단 코드만 남겨보겠다.

 

#include <stdio.h>

int main(void){
    int arr[5] = {5, 1, 7, 10, 3};
    int i, j, temp=0, len=sizeof(arr)/sizeof(int);    //배열의 길이를 구한다.
    
    printf("#1. 버블소트\n");

    printf("input : [");
    for(i=0; i< len; i++){
        printf(" %d", arr[i]);
    }
    printf("]\n");

    for(i=0; i < len; i++){    //버블소트
        for(j=0; j < len-1; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }

    printf("Result: [");
    for(i=0; i< len; i++){
        printf(" %d", arr[i]);
    }
    printf("]\n");
    
    return 0;
}

 

결과

 

그래도 결국 PC로 돌려서 결과를 찍어냈다.

 

 

 

 

 

---

~ 광고 타임 ~

---

 

 

 

끝.