버블 정렬(Bubble Sort Algorithm)

버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다.

오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.
맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼만 반복해주면 된다.

 

1. 삽입 정렬은 두번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전의 인덱스 값을 비교한다.

2. 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다.

3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다.

4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

 

이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개, n-2개...1개씩 비교를 반복하며,

선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(N^2)이다.

공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(N)이다.

 

let bubbleSort = function(array) {

  let leng = array.length;

  for (let i = 0; i < leng; i++) {
    for (let j = 0; j < leng - i - 1; j++) {
      // 한바퀴를 돌때마다 제일 끝으로 제일 큰 숫자가 가기때문에
      // (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 순회
      if (array[j] > array[j + 1]) {
        let tmp = array[j + 1];
        array[j + 1] = array[j];
        array[j] = tmp;
      }
      // 계속 배열을 순회하면서 전 인덱스와 현 인덱스의 숫자를 비교하면서 값을 바꿔 나감
    }
  }

  return array;
};

// 시간복잡도 : O(N^2)