내용이 안 보인다면 쿠키/캐시를 지우고 새로고침 하세요!
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌5 - Algorithm - 2년 전 등록

버블(거품) 정렬(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- 무단 전재 및 재배포 금지

댓글

아직 댓글이 없습니다.