버블 정렬 (Bubble Sort)

: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘

• 정렬이 이루어지는 방식이 '마치 거품이 밀려 올라가는 모습'과 같아서 bubble sort라고 부른다.
• 더 이상의 스왑(swap)이 일어나지 않을 때, 배열이 정렬된 것이다.

입출력 예

의사 코드

function bubbleSort() {
  let swapped; 스왑되었는지 기록하는 변수를 만든다.
  
  do {
    기본적으로 swapped을 false로 초기화해준다.
    
    반복문(반복문을 순회하며 arr[i]와 arr[i + 1]을 비교한다.) {
      
        만약 (arr[i]가 arr[i + 1]보다 크다면) {
          둘의 위치를 바꿔주고, 스왑이 일어났으므로 swapped를 true로 바꿔준다.
      } 그 외의 경우는 바꿔주지 않아도 되므로 그대로 둔다.
    }
    
  } while(위의 반복문을 반복한다. 언제까지? for 반복문에서 요소가 한 번이라도 스왑된 적이 있다면)
  
  정렬된 배열을 반환한다.
}

두 변수를 바꾸는 방법

1. 임시 변수 활용

let temp = arr[idx1]; // 임시 변수에 arr[idx1]의 값을 저장해둔다.
arr[idx1] = arr[idx2];
arr[idx2] = temp;

2. 구조 분해 할당(Destructuring assignment) 활용

// 배열이 reference type이라 가능하다.
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

3. XOR 연산 활용

// 배열이 reference type이라 가능하다.
arr[idx1] ^= arr[idx2];
arr[idx2] ^= arr[idx1];
arr[idx1] ^= arr[idx2];

풀이

function bubbleSort(arr) {
  let swapped;
  
  do {
    swapped = false;
    
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    
  } while (swapped);
  
  return arr;
}

버블 정렬은 O(n²)의 시간복잡도를 가진다.

이 글은 아래 링크를 참고하여 작성한 글입니다.
JavaScript Algorithms - 20 - Bubble Sort
JavaScript Algorithms - 21 - Bubble Sort Solution