[알고리즘] 버블 정렬 (Bubble Sort)

오늘은 첫 알고리즘 공부 시작이다. 정보처리기사 자격증 공부하면서 이것저것 들어보긴 했지만 자세히 알아본적은 없기 때문에 제대로 알고 넘어가겠다.

정렬(sort)이란 입력으로 주어진 숫자를 작은 순으로 나열하는 것을 말한다.

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

버블 정렬(Bubble Sort)은 오른쪽에서 시작하여 왼쪽 방향으로 인접한 두 숫자를 비교하여 교체하는 작업을 반복한다.

오른쪽에서 왼쪽으로 숫자가 이동해 가는 모습이 물속에서 공기가 떠어르는 것과 비슷하다고 붙은 이름이라고 한다.

1부터 9까지 랜덤으로 배치된 수열을 버블 정렬로 정렬해 보겠다.

먼저 가장 오른쪽 부터 인접한 왼쪽 수랑 비교한다. 비교한 결과, 오른쪽 숫자가 더 작으면 왼쪽과 바꿔준다.

가장 오른쪽에 있는 3과 인접한 8과 비교해주면 8 > 3 이기 때문에 숫자를 교체한다.

비교를 완료하면 한칸 옮겨 같은 방법으로 숫자를 비교한다. 이번엔 1 > 3 이기 때문에 변경하지 않는다.

다음 한칸 옮겨 두 수를 비교하면 6 > 1 이기 때문에 변경해 준다.

이런식으로 한칸씩 옮기다 보면 가장 작은 숫자인 1이 가장 왼쪽으로 정렬이 된다. 이렇게 가장 오른쪽부터 왼쪽까지 오면 1라운드가 끝났다.

그럼 가장 왼쪽에 있는 숫자는 정렬이 끝난 것으로 간주하고 다시 가장 오른쪽으로 간다. 그리고 동일한 방법으로 정렬해 준다.

2라운드가 종료된 모습이다. 다음 작은 수인 2가 가장 왼쪽으로 정렬이 되었다.

같은 방식으로 3, 4라운드를 정렬하고..

5라운드..

6라운드 까지 진행을한 결과 정렬이 완료되었다.

이해하기 쉬운 정렬이라 빠르게 정리해 보았다.

버블 정렬은 1라운드에서 n-1회, 2라운드에서 n-2회.. n-1라운드에서 1회 비교한다.

따라서 비교 횟수는 n² / 2 이다. 이 비교 횟수는 입력 데이터의 순서와 상관없이 일정하다.

버블 정렬의 장점은 구현이 간단하다는 점이 있지만, 단점이 더 많다.

순서와 맞지 않게 인접한 요소와 교환이 된다는 점

하나의 요소가 가장 왼쪽으로 이동하기 위해서 모든 요소가 움직여야 된다는 점

특정 요소가 이미 최종 정렬 위치에 위치하여도 교환 되는 경우가 있다는 점

그리고 자료를 교환(Swap)하는것이 이동(Move)시키는 작업이 복잡하기 때문에 버블 정렬은 잘 사용되지 않는다.

숫자의 교체 횟수는 입력 데이터에 따라 달라진다. 극단적인 경우, 입력 데이터가 우연히 작은 순서대로 나열되 있으면 한 번도 교체하지 않는다. 반대로 숫자가 큰 순서대로 나열된 경우에는 비교할 떄마다 교체해야한다. 따라서 버블 정렬 계산 시간은 O(n²)이다.

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

[알고리즘] 버블 정렬(bubble sort)이란 : Heee's Development Blog https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

코딩 블로그