게시글

강좌5 - Algorithm - 3년 전 등록

버블(거품) 정렬(bubble sort)

조회수:
0

안녕하세요. 이번 시간에는 기본적인 정렬 중 하나인 버블 정렬에 대해 알아보겠습니다. 이렇게 이름지어진 이유는 정렬하는 모습이 거품이 꺼지는 모습과 비슷하기 때문입니다. 실제로 흩어져있는 데이터들이 서로 바뀌면서 일렬로 정렬되는데 그 모습이 정말 보기 좋습니다. 링크에 버블 정렬에 대한 움짤이 있습니다.

아쉽게도 위키피디아에는 자바스크립트로 구현된 버블 정렬 코드가 없기 때문에 제가 직접 보여드리겠습니다. (없어서 다행입니다.) 버블 정렬은 O(n^2)이기 때문에 성능이 좋지 않습니다. 거기에 성능이 안 좋은 정렬 중에서도 가장 안 좋은 편에 속하는 정렬이라, 주로 알고리즘 교육용을 제외하고는 사용되지 않습니다. 먼저 간단한 예제를 볼까요?

[5,1,7,4,6,3,2,8] 처음 두 수를 비교해서 순서대로 숫자를 서로 바꿔줍니다.
[1,5,7,4,6,3,2,8] 5와 7은 이미 정렬되어 있으니까 그대로 놔둡니다.
[1,5,7,4,6,3,2,8] 7과 4는 서로 바꿔줍니다.
[1,5,4,7,6,3,2,8]
[1,5,4,6,7,3,2,8]
[1,5,4,6,3,7,2,8]
[1,5,4,6,3,2,7,8] 끝까지 정렬을 했으면 다시 처음부터 비교합니다.
[1,5,4,6,3,2,7,8]
[1,4,5,6,3,2,7,8] 5,6은 넘어가고 6,3 순서를 바꿔줍니다.
[1,4,5,3,6,2,7,8]
[1,4,5,3,2,6,7,8] 다시 처음부터 비교합니다.
[1,4,3,5,2,6,7,8]
[1,4,3,2,5,6,7,8] 다시 처음부터
[1,3,4,2,5,6,7,8]
[1,3,2,4,5,6,7,8] 다시 처음부터
[1,2,3,4,5,6,7,8] 정렬 끝

정렬 과정이 엄청 길죠? 한 과정에 겨우 두 수의 위치를 서로 바꾸는 작업밖에 못합니다. 성능이 좋을 리가 없죠. 하지만 간단한 작업을 하는 만큼, 코드를 짜기는 쉽습니다. 코드로 볼까요?

var bubbleSort = function(array) {
  var length = array.length;
  var i, j, temp;
  for (i = 0; i < length - 1; i++) { // 순차적으로 비교하기 위한 반복문
    for (j = 0; j < length - 1 - i; j++) { // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
      if (array[j] > array[j + 1]) { // 두 수를 비교하여 앞 수가 뒷 수보다 크면
        temp = array[j]; // 두 수를 서로 바꿔준다
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};

bubbleSort([5,1,7,4,6,3,2,8]);

코드는 간단하지만 반복문을 두 번 중첩해서 돌기 때문에 성능이 안 좋습니다. 처음 삽입 정렬 시간에도 반복문을 두 번 돌아서 성능이 별로였죠. 다행히 return 값은 array라 메모리를 더 차지하지는 않습니다. 뭐 어차피 앞으로 버블 정렬을 사용하는 일은 없을 겁니다. 다음 시간에는 선택 정렬에 대해 알아보겠습니다!

투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.

댓글

1개의 댓글이 있습니다.
2달 전
반복문에서 -1 또는 -1 -i를 하지 않아도 결과 값이 나오는데 위와 같은 방식으로 구현해야 하는 건가요? -1 과 -1 -i를 하는 이유가 궁금합니다.