[Algorithm] 버블 정렬

버블 정렬

인접한 두 요소를 비교하여 서로 스왑하는 방식으로 정렬하는 알고리즘

예시) 숫자 오름차순 정렬 (JS)

대상배열

let arr = [6, 4, 7, -1];

정렬방식

'i' 번째 요소가 'i+1' 번째 요소보다 크면 => 위치 SWAP // arr[i] > arr[i+1]
'i' 번째 요소가 'i+1' 번째 요소보다 작으면 => 그대로 둔다

첫번재 인덱스 vs 두번째 인덱스, 두번째 인덱스 vs 세번째 인덱스... 반복

STEP-1 : 각 요소를 순서대로 비교해 제일 큰 값을 맨 뒤로 보낸다

[6, 4, 7, -1] → [4, 6, 7, -1] → [4, 6, 7, -1] → [4, 6, -1, 7] // 7이 맨뒤로 이동

STEP-2 : 두번째로 큰 값을 뒤에서 두번째로 보낸다

[4, 6, -1, 7] → [4, 6, -1, 7] → [4, -1, 6, 7] // 마지막 7이랑은 굳이 비교 안해도 됨

STEP-3 : 세번째로 큰 값을 뒤에서 세번째로 보낸다

[4, -1, 6, 7] → [-1, 4, 6, 7] // 4 vs -1 스왑

CODE

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

OPTIMIZED

const bubbleSort = (arr) => {
  let swapped = false; // 스왑여부 확인 변수 추가
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true; // 스왑시 true로
      }
    }
    
    if (swapped === false) break; // 스왑될거 없으면 빠져나오기
  }

  return arr;
};