버블 정렬

버블 정렬에 대해 알아봅니다.

버블 정렬

 

버블 정렬

 

1. 버블 정렬이란 무엇이고, 어떻게 이뤄지는가?

2. 코드로 살펴보기

 

1. 버블 정렬이란 무엇이고, 어떻게 이뤄지는가?

 물 속에서 물방울이 수면 위로 올라오는 것처럼 가장 큰 수가 계속 오른쪽으로 자리를 옮겨가면서 진행되는 정렬 알고리즘이다. 이중 반복문으로 진행되며, 각 회차마다 인접한 두 요소 (앞, 뒤)를 비교하고 앞의 요소가 뒤 요소보다 클 시 자리를 교환한다.
 이중 반복문을 사용하여 시간 복잡도는 항상 n^2으로 배열의 크기가 클수록 실행 시간이 크게 늘어난다.

2. 코드로 살펴보기

function bubbleSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {
  // 배열의 전체 요소를 조회합니다. 단, 앞, 뒤 요소를 비교하므로 len - 1 미만으로 범위를 지정합니다.
  // 만약 len 미만으로 지정할 시, 맨 마지막 요소는 비교할 대상이 없어 문제가 발생합니다.
  
    for (let j = 0; j < len - 1 - i; j++) {
    // j의 범위는 len -1 -i 미만으로 지정합니다. len -1 -i 이상 인덱스 요소들은 이전 회차에서
    // 이미 정렬이 된 요소 이므로 다시 비교를 진행하지 않습니다.
    
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        // 만약 앞의 요소가 뒤의 요소보다 클 시, 위치를 변경합니다.
        
      }
    }
  }

  return arr;
}