티스토리 뷰

코드 스니펫 복사

C언어 정렬 - 버블정렬(Bubble Sort) 쉽게 정리하기



버블 정렬(Bubble Sort)은 두 인접한 원소를 검사하여 정렬하는 방법입니다. 
 

버블 정렬(Bubble Sort)은 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용되는데요. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고 하네요.

버블 정렬(Bubble Sort)
- 두 인접한 원소를 검사하여 정렬하는 방법
- 시간 복잡도 O(n^2)
- 코드가 단순하기 때문에 자주 사용됨 





버블 정렬 알고리즘 실행 과정 해부하기



버블 정렬 알고리즘의 실행 과정을 보도록 하겠습니다.
 

이 버블 정렬 알고리즘은 인접한 두 수를 비교해서 큰 수를 뒤로 보내는 알고리즘이라고 위에서 설명한 바 있는데요. 이번에는 실제 예제를 통해서 그 과정을 눈으로 확인해 보도록 하겠습니다.


예를 들어 아래와 같이 다섯 개의 숫자가 있다고 가정하고 과정을 설명하도록 하겠습니다.

6

4

7

9

1


에서 먼저 6, 4를 비교하여 6이 더 큰 수이므로.. 두 수의 자리를 교체합니다.
 

6

4

7

9

1

4

6

7

9

1


다시 오른쪽으로 한칸 이동해서 6, 7을 비교합니다. 여기서는 7이 크므로 교환이 없습니다.

4

6

7

9

1

 

다시 오른쪽으로 한칸 이동해서 7, 9를 비교합니다. 여기서는 9이 크므로 교환이 없습니다.

4

6

7

9

1

 

다시 오른쪽으로 한칸 이동해서 9, 1를 비교합니다. 여기서는 9가 크므로 두수를 교환합니다.
 

4

6

7

9

1

4

6

7

1

9


다시 맨 처음으로 돌아와서 4, 6을 비교합니다. 6이 크므로 다음으로 진행합니다.

4

6

7

1

9


다시 오른쪽으로 한칸 이동해서 6, 7을 비교합니다. 7이 크므로 다음으로 진행합니다.

4

6

7

1

9

4

6

7

1

9


다시 오른쪽으로 한 칸 이동해서 7, 1을 비교합니다. 7이 크므로 두 수를 교환합니다.

4

1

7

1

9

4

1

1

7

9


다시 오른쪽으로 한 칸 이동해서 7, 9를 비교합니다. 9가 크므로 다음으로 진행합니다. 

4

1

6

7

9


다시 처음으로 가서 4, 1을 비교합니다. 4가 크므로 두 수를 교환합니다.

4

1

6

7

9

1

4

6

7

9


나머지도 인접한 두 수를 비교하면서 진행합니다...
정렬이 다 되었으니 나머지 과정은 생략합니다.
 

잘 보셨나요? 위의 과정과 같이 버블 정렬이 진행됩니다.



버블 정렬(Bubble Sort) 알고리즘 분석



버블 정렬(Bubble Sort)의 알고리즘을 분석해보도록 하겠습니다.

먼저 메모리 사용 공간을 보면 아래와 같이 n개의 원소를 저장하므로 n개의 메모리를 사용하게 됩니다.

6

4

7

9

1



그 다음으로는 연산 시간에 따른 최선, 최악의 경우를 비교해 보도록 하겠습니다.

최선의 경우는 자료가 이미 정렬되어 있는 경우입니다. 아래와 같이 정렬되어 있는 경우, 비교횟수는 i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번이고 자리교환이 발생하지 않으므로 자리교환횟수는 0번입니다.

1

4

6

7

9


 
최악의 경우는 자료가 역순으로 정렬되어 있는 경우입니다.
이 경우 비교횟수는 i번째 원소를 (n-1)번 비교하므로, n(n-1)/2번이고 자리교환횟수는 i번째 원소를 (n-1)번 교환하므로 n(n-1)/2번이 됩니다.

9

7

6

4

1


 

버블 정렬 알고리즘 분석


* 메모리 사용 공간

n개의 원소에 대하여 n개의 메모리 사용


* 연산 시간

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


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

:: 자리교환횟수 : 자리교환이 발생하지 않음


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

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

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


평균 시간 복잡도O(n^2)이 됨


 




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

 
 
버블 정렬(Bubble Sort) 알고리즘 소스를 보도록 하겠습니다.


 #include<stdio.h>

int main()
{
    int arr[5]={6,4,7,9,1};
    
	int i,j,tmp;
    
	// 정렬 전 배열값 출력
	printf("===== 버블정렬 전 =====\n");
    for(i=0;i<5;i++) printf("%3d",arr[i]);
	printf("\n");

	// 버블정렬
	for(i=0;i<5;i++) 
    {
        for(j=0;j<4;j++)
        {
			// 앞의 수, 바로 뒤의 수 비교해서
			// 앞의 수가 클 경우 값을 교환
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }

	// 버블 정렬 결과 출력
	printf("===== 버블정렬 후 =====\n");
    for(i=0;i<5;i++) printf("%3d",arr[i]);
	printf("\n");

	return 0;   
}


위의 소스를 실행한 결과입니다.



위 소스의 핵심소스는 아래 부분이 되겠습니다.

 
// 버블정렬
	for(i=0;i<5;i++) 
    {
        for(j=0;j<4;j++)
        {
			// 앞의 수, 바로 뒤의 수 비교해서
			// 앞의 수가 클 경우 값을 교환
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }

궁금하신 것이 있으시면 댓글 남겨주세요^^


댓글
  • 프로필사진 anonymous 6,4를 비교하였을때 6이 크므로 서로 자리를 바꾸고 그 다음단계로 넘어가야 하는데, 다음단계에서는 자리를 바꾸지 않고 그대로 쓰신 것 같네요. :) 2013.11.14 18:57 신고
  • 프로필사진 하늘과 나 잘못된 부분 수정했습니다. 정말 고맙습니다^^ 2013.11.14 19:08 신고
  • 프로필사진 비밀댓글입니다 2014.04.08 21:41
  • 프로필사진 하늘과 나 알고리즘 소스는 알고리즘을 소스로 구현한 것이에요. 물론 방법은 여러가지가 있을 수 있어요.
    그리고 주석을 단 것은 소스에 대한 설명을 한 것입니다^^
    2014.04.08 22:07 신고
  • 프로필사진 eng // 버블정렬
    for(i=0;i<5;i++) <---- 왜 이 반복문이 여기서 들어가는 거죠????
    {
    for(j=0;j<4;j++)
    {
    // 앞의 수, 바로 뒤의 수 비교해서
    // 앞의 수가 클 경우 값을 교환
    if(arr[j]>arr[j+1])
    {
    tmp=arr[j];
    arr[j]=arr[j+1]; <--- 이 부분 자리 교환 한다는게 도무지 이해가 안가네요....??
    arr[j+1]=tmp;
    }
    }
    }
    2014.04.13 02:14 신고
  • 프로필사진 yum08901 맨 처음 반복문이 들어가는 이유는 이중포문을 써야하기 때문입니다. 만약 저기서 저 포문을 빼게 된다면 정렬은 한번만 이뤄지고 더 이상 돌아가지 않겠죠.

    또 arr[j] = arr[j+1]; 이 부분을 왜 해주었느냐, 그건 이제 메모리를 봐야하는데요.그냥 단수히 저 부분을 빼고 돌려주게 되면 값은 안 바뀌고 그냥 넘어가게 됩니다. 이 부분은 말로 설명하기 좀 힘드네요; 암튼 저 코드는 맞는 코드이니 걱정안하셔도 됩니다.
    2014.09.15 00:04 신고
  • 프로필사진 ksj for(j=0;j<4-i;j++) 가 맞는것 같네요.. 2014.07.03 16:47 신고
  • 프로필사진 Arksh 제 블로그에 링크해도 되겠죠? 잘 봤습니다. 2015.01.09 16:38 신고
  • 프로필사진 하늘과 나 네^^ 2015.01.09 22:54 신고
  • 프로필사진 ybi 쌩둥맞은 궁금한 질문인데..
    배경 줄 색깔 흰색/회색 저렇게 보기 편하게 하려면 어떻게해야하나요?? ^^;;
    2015.02.04 22:05 신고
  • 프로필사진 하늘과 나 syntax highlighter를 사용하시면 됩니다^^ 아래의 링크를 참고하세요^^ http://alexgorbatchev.com/SyntaxHighlighter/download/ 2015.02.05 00:24 신고
  • 프로필사진 망원경 정말 감사합니다!!! 공부하는데 좋은 참조가 되었습니다! 2015.10.21 16:05 신고
  • 프로필사진 하늘과 나 감사합니다^^ 2015.10.21 16:13 신고
  • 프로필사진 김슬기 안녕하세요!!!

    버블 정렬 공부하는데 많은 도움을 받고 갑니다.

    제가 개인적으로 공부하면서 블로그에 정리를 하곤 하는데

    내용이 좋아서!!! 링크 걸어두고 싶어서요

    혹시, 원하지 않으시면 알려주세요!!! 지우도록 할께요
    2015.11.23 13:43 신고
  • 프로필사진 하늘과 나 링크는 얼마든지 환영합니다^^ 2015.11.23 13:43 신고
  • 프로필사진 행인 4 6 7 1 9 뒤에
    다시 처음으로 가서 4 6 을 비교하는 부분에서는
    4 6 1 7 9 로 순서가 바뀌네요..
    뭔가 잘못된거 같습니다..!
    2016.03.08 10:30 신고
  • 프로필사진 하늘과 나 지적 감사합니다.
    행인님의 말씀처럼 틀린 부분이 있었네요.
    수정했습니다.
    2016.03.08 16:25 신고
  • 프로필사진 ㅇㅅㅇ 내부 for문 왜 이미 정렬완료된 것들까지 굳이 다 비교하죠?
    for(j=0; j<4-i; j++) 아닌가요?
    2016.03.30 18:01 신고
  • 프로필사진 zjadkfaht 숫자를 6개가 아니라 10개로 하려면 어디를 수정해야하나요?? 2016.05.10 21:24 신고
  • 프로필사진 섹스킹 감사함당 덕분에 이해됬어요 2016.06.28 21:17 신고
  • 프로필사진 호리 원소들끼리 정렬이 다 된 경우 비교하지 않아도 되잖아요 그때 알고리즘은 어떻게 작성헤야하는지 감이 오지를 않네요 버블정렬 원리는 파악했는데 ㅠㅠ 2016.12.02 19:38 신고
  • 프로필사진 호리병 break 해서 넘기면되지않나용? 2016.12.06 15:00 신고
  • 프로필사진 ㅇㅇ 코드 틀렸네요. 틀렸다기 보단 비효율적인 코드. 일반적으로 버블정렬은 정렬 끝난 부분은 재검사 하지 않습니다 2017.05.30 19:51 신고
  • 프로필사진 연지강 숫자말고 가나다순 이름을 버블정렬하려면 어떻게해야하나요../?
    숫자는 정상적으로 버블정렬이 되는데 문자로 처리하니 정렬이안되그 그대로 출력됩니다 ㅠ
    2017.12.03 22:51 신고
  • 프로필사진 123 버블 정렬은 이거에요
    int array[]={5,4,3,2,1};
    size=sizeof(array)/sizeof(int);
    for(int i=0; i<size-1;i++){
    for(int j=0; j<size-i-1; j++){
    if(array[j]>array[j+1])
    swap();
    }
    }
    2018.01.25 21:07 신고
댓글쓰기 폼
공지사항
Total
2,611,103
Today
316
Yesterday
820
«   2018/02   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28      
글 보관함