[Javascript] Bubble Sort (버블 정렬) 구현 코드

Bubble Sort (버블 정렬)

인접한 두 수를 비교해서 가장 큰 수를 뒤쪽으로 보내는 방식.

수도코드

// 기본
1. 이중 반복문 선언
  1-1. 첫 번째 반복문 : 가장 큰 수를 제외한 범위 규정
  1-2. 두 번째 반복문 : 범위 내 순회
    2. j번째 요소와 j+1번째 요소를 비교
    3. j번째 요소가 더 크다면 스왑
4. 정렬된 배열 리턴 

👇 아래는 flag를 사용한 수도코드. 버블 정렬의 최악의 경우는 이미 정렬된 배열을 도는 경우이다.
두번째 반복문을 도는 동안 한 번도 swap이 일어나지 않으면 이미 정렬된 배열이므로 반복문을 중지시킨다.

// flag 사용
0. flag 선언
1. 이중 반복문 선언
  1-1. 첫 번째 반복문 : 가장 큰 수를 제외한 범위 규정
  1-2. 두 번째 반복문 : 범위 내 순회
    2. j번째 요소와 j+1번째 요소를 비교
    3. j번째 요소가 더 크다면 스왑
    4. 스왑 후 flag 변화
  5. 두 번째 반복문을 다 돌고도 flag에 변동이 없다면 첫 번째 반복문 break
6. 정렬된 배열 리턴 

코드 구현

1. 기본

const arr = [3, 1, 8, 23, 33, 12, 5, 36, 81];

// swap 헬퍼함수
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

const result = buubleSort(arr);
console.log(result); // [1, 3, 5, 8, 12, 23, 33, 36, 81]

2. flag 사용

const arr = [3, 1, 8, 23, 33, 12, 5, 36, 81];

// swap 헬퍼함수
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

function bubbleSort2(arr) {
  let isSorted = false;
    for (let i = arr.length - 2; i >= 0; i--) {
      isSorted = true;
      for (let j = 0; j <= i; j++) {
	if (arr[j] > arr[j + 1]) {
	  swap(arr, j, j + 1);
	  isSorted = false;
        }
    }
    if (isSorted) break;
    }
  return arr;
}

const result = bubbleSort2(arr);
console.log(result); // [1, 3, 5, 8, 12, 23, 33, 36, 81]