버블정렬 알고리즘(bubble sort)

버블정렬(bubble sort) - 정렬 알고리즘을 배울때 보통 먼저 배우는 정렬 알고리즘 입니다.

 버블정렬은 간단하기 때문에, 직관적으로 쉽게 이해할 수 있습니다.


마치 거품이 수면으로 올라오는 것 같아서 버블정렬이라고 한다네요.


버블정렬을 설명하기에 앞서 주요 정렬 알고리즘에 관한 시각적 자료를 링크하겠습니다. 


정렬들간에 비교와 정렬의 특성을 파악할 수 있습니다.



버블정렬은 사람의 입장에서는 그렇게 자연스럽지 않습니다. 위 영상처럼 두 개씩 대소관계를 비교하며 위치를 바꾸어 나가는 데 컴퓨터 가 살아있다면 컴퓨터 입장에서 이러한 단순함이 오히려 쉽다고 느껴질꺼라 생각합니다.

버블 소트의 문제해결 방법은 다음과 같습니다.

1. 배열의 첫번째 요소와 두번째 요소의 대소관계를 비교한다

2. 대소관계에 따른 위치를 바꾼다.

3. 비교하는 배열의 첨자(요소의 번호,위치)를 하나씩 증가하여 1,2번을 되풀이한다.

4. 배열의 끝 요소까지 비교했으면 처음부터 위 작업을 반복하되 바로 앞에서 비교했던 요소 중 제일 마지막 첨자는 제외한다.

이런식으로 비교하면 배열의 맨 뒤에서부터 큰수가 차례대로 채워지게 됩니다.

위 방법은 (배열 요소의 개수 -1)번의 루프안에 (1부터 (배열요소의 개수-1)까지의 합)의 루프가 돌아갑니다.


다음은 크기순서 관계없이 무작위로 나열된 크기 5인 배열을 버블정렬(bubble sort)을 이용해 정렬하는 그림입니다.




붉은 부분은 문제해결 방법의 순서 1에 해당됩니다. 만약 대소를 비교하여 바꿀 필요가 없다면 2번은 수행되지 않습니다. 이렇게 배열을 끝까지 비교를 마치면 배열의 끝에는 비교한 수 중 가장 큰 수가 있게 됩니다.

위에 44의 수는 더이상 비교할 필요가 없습니다. 제외를 하고 문제해결방법의 1,2번을 배열의 첫째 요소부터 반복합니다.


이런 식으로 나머지 세계의 수에 대해서도 마무리하면 모든 루프가 끝나고 배열은 크기 순서대로 정렬이 되게 됩니다.

다음은 위 배열에대한 버블정렬을 하는 코드입니다.

코드는 매우 간단합니다. 배열에 대한 이해와 각 루프간에 상관관계를 파악한다면 쉽게 분석할 수 있습니다.


위 코드는 버블정렬의 기본적인 생각이 반영되어 있지만, 세련되지는 못합니다. 이유는 다음과 같습니다.

2,4,23에 대해서 문제해결방법 1,2를 시행하지만 쓸모없는 시행이 되어버립니다. 이렇게 정렬이 다 된 경우에도 나머지 수행을 하는 것은 매우 낭비적인 일이고, 배열의 크기가 클 수록 자원낭비가 커지게 됩니다.

해결 방법은 일종의 플래그를 설정하여, 앞의 시행에서 문제해결방법 2번의 시행이 한 차례도 일어나지 않는 다면 정렬이 다 된 것으로 간주해도 좋습니다. 


만약 flag가 변화하지 않는다면 문제해결 2번이 한 차례도 실행되지 않은 것이므로 break로 루프를 빠져나갑니다.


http://www.sorting-algorithms.com/

위에 링크된 주소로 가면 각 정렬들간 비교를 할 수 있습니다. 버블 정렬은 단순한 만큼 속도면에서 매우 비효율적인 정렬입니다. 앞으로 여러 정렬들을 포스팅하며 효율적인 정렬방법과 여러 상황에 맞는 정렬 방법을 정리해 가도록 하겠습니다.

반응형
이 댓글을 비밀 댓글로
  1. 까먹고 있었는데, 버블정렬 다시 한번 되새기고 갑니다.
    • 익명
    • 2017.05.03 00:07
    비밀댓글입니다
      • 댓글테스트
      • 2017.05.03 00:08
      관리자의 승인을 기다리고 있는 댓글입니다
    • 안녕하세요. 제가 약간 술에 취해서 정신없게 대답할 수도 있겠지만, 우선 답변드리겠습니다.
      i의 값은 첫번째 for문에 의해서 0부터 n-1까지 증가합니다.
      0, 1, 2, ..... n-2까지요.
      그리고 두 번재 for문은 j의 값이 0부터 시작해서 n-1+i까지 for문이 돌아가죠?
      여기서 i의 값은 앞에서 0부터 n-1가지 증가한다고 했습니다. 그러면 두 번재 for문을 풀어쓰면
      0부터 n-1까지
      0부터 n-2까지
      0부터 n-3까지
      0부터 n-4까지
      0부터 n-5까지
      ....

      i의 값이 증가할 수록 for문의 범위는 하나씩 줄어드는 겁니다. 다음그림처럼요.
      ㅁㅁㅁㅁㅁㅁㅁ■ i가 0일때
      ㅁㅁㅁㅁㅁㅁ■■ i가 1일때
      ㅁㅁㅁㅁㅁ■■■ i가 2일때
      ㅁㅁㅁㅁ■■■■ .....
      ㅁㅁㅁ■■■■■ ....
      ㅁㅁ■■■■■■ ....
      ㅁ■■■■■■■ ....
      따라서 두번 째 for문은 첫 번째 for문에 의해서 i값이 하나씩 증가할 때마다 for문의 범위가 하나씩 줄어듭니다. 즉 요소 ㅁ에 대해서만 for문을 돌리게 됩니다.
      ■는 정렬이되어 확정된 수 입니다. 확정된 수에 대해서는 정렬을 할 필요가 없죠.

      이렇게 첫 번째 for문에서 i의 역할은 정렬할 요소를 하나씩 줄이는 역할을 합니다.
    • 당직메르시
    • 2017.05.03 00:09
    죄송한데 비밀 댓글 답변을 오픈으로 해주실 수 있나요ㅠㅠ
    비밀 댓글 보는 방법을 모르겠습니다......
    • ㅇㅇㅇ
    • 2017.06.29 18:56
    버블정렬의 예시에는 무엇이 있나요?
    • 안녕하세요. 버블정렬은 성능이 안좋은 알고리즘이므로 실용적으로 그리 쓰이지 않습니다.
      다루는 아이템의 개수가 적은 경우에 쓰일수는 있겠네요. 모든 정렬알고리즘은 프로그래밍을 하면서 참 많이 쓰입니다. 게임의 경우 아이템 인벤토리를 정렬할 때도 쓰일 수 있고, 단어장 프로그램, 사전 프로그램 같은 경우 단어를 사전 순서대로 정렬할 때도 쓰입니다. 버블 정렬 또는 퀵정렬, 쉘정렬 등 어떤 것을 써도 결과는 같지만 알고리즘의 성능은 절대적이지 않으므로 사용용도에 최적화된 알고리즘을 사용해야합니다.