[알고리즘] 버블 정렬 Javascript로 구현하기

버블 정렬 (Bubble sort)

버블 정렬은 정렬 알고리즘 중 하나이다. 

시간 복잡도는 O(n^2)으로 느리다. 하지만 간단하기에 자주 쓰인다. 

배열에서 순차적으로 인접한 원소를 비교하고 교체하는 방식이다.

원소가 교체되며 이동하는 방식이 마치 수면위로 떠오르는 거품같아 버블 정렬이라 부른다. 

밑의 예제로 쉽게 배워보자.

 

버블 정렬 예제 (Javascript)

자바스크립트로 버블 정렬을 구현해보자.

배열 : [13, 5, 11, 7, 23, 15] 
주어진 배열을 오름차순으로 버블 정렬을 이용해 정렬해보자. 

먼저 주어진 배열의 array[0], array[1] 값을 비교한다.

array[1] = 5, array[0] = 12로 array[1]의 값이 더 작다. 

우리가 원하는 정렬은 오름차순이므로 작은 값일수록 앞에 위치하여야 한다. 그리하여  array[1]과 array[0]을 서로 교체한다. 

 

다음은 array[1]과 array[2]를 비교해보자. 

array[1] = 12, array[2] = 11로  array[2]값이 더 작다. 

array[1]과 array[2]값을 교체해준다. 

 

이 패턴대로 인접한 인덱스끼리 값을 비교하며 자리를 교체한다. 

그리하여 한바퀴를 돌면 배열은

배열: [5,11,7,12,15,22] 

이렇게 정렬된다.

 

이제 다시 같은 패턴으로 배열의 첫 인덱스부터 다시 돈다. 

이렇게 두번째 바퀴를 돌아서 

배열: [5,7,11,12,15,22] 가 된다.

 

이 패턴을 반복해 나가며 버블 정렬이 수행된다. 

 

이를 자바스크립트 코드로 구현하면 다음과 같다.

function solution(array) {
  let answer = array;
  for (let i = 0; i < array.length; i++) {
    let p = 0;
    while (p <= array.length - 2) {
      if (answer[p] > answer[p + 1]) {
        [answer[p], answer[p + 1]] = [answer[p + 1], answer[p]];
      }
      p++;
    }
  }
  return answer;
}

1. for (let i = 0; i < array.length; i++) 은 배열의 길이만큼 돌면서 정렬을 수행하게 한다. 
2. let p = 0; 은 비교할 인덱스값을 담는다.
   array[0],array[1] 비교 -> array[1],array[2] 비교, -> array[2],array[3]비교 ->...
   여기서 0,1,2,... 값이 p가 되는 것이다. 
3. while (p <= array.length - 2) 는 p값이 배열의 길이 - 2 보다 작거나 같은 경우까지만 코드를 반복하도록 한다. 
4. if (answer[p] > answer[p + 1]) {
           [answer[p], answer[p + 1]] = [answer[p + 1], answer[p]];
   }
   p++;
   이 코드는 while문 안에서 동작하는 코드이다. 배열의 p 인덱스의 값과 p+1값을 비교하고 자리를 교체하는 코드이다.

 

---

도움이 되셨다면 ♥︎를 눌러주시면 큰 힘이 됩니다