<aside> 💡 예시의 모든 input은 [10, 7, 9, 5, 1]로 통일. 버블 / 선택 / 삽입 정렬 모두 최악의 경우 O(n²) 시간복잡도를 갖는다. 알고리즘 성능이 좋지 않아 거의 쓰진 않지만, 적은 데이터를 정렬할 땐 유용.

</aside>

버블 정렬 | Bubble Sort

[10, 7, 9, 5, 1] 배열을 버블 정렬하는 과정

거품이 일어난 것처럼 배열의 각 요소들이 순차적으로 정렬돼서 버블 정렬이라고 부른다. 두 요소를 묶어서 비교한 후 큰 숫자를 오른쪽으로 밀어낸다. i번째 정렬을 마칠때마다 “뒤에서 i번째” 자리의 순서가 확정된다.

시간 복잡도 (삽입 정렬과 동일)

• Worst Case(정렬이 전혀 안됐을 때) : O(n²) — 중첩 반복문을 사용하므로
• Best Case(이미 정렬됐을 때) : O(n)

장단점 (삽입 정렬과 동일)

<aside> 💡 용어 설명

• Stable 정렬 : 중복 데이터는 순서를 바꾸지 않는 방식(Unstable 정렬은 중복 데이터도 순서 바꿈)

• In-place 정렬 : 새로운 배열 생성 없이 기존 배열만 사용하거나, 충분히 무시할만한 저장 공간만 더 사용하는 정렬 방식(Not In-place 정렬은 요소 개수에 비례하는 저장공간을 더 사용함) </aside>

• 장점 : 구현하기 쉽고, in place 알고리즘으로 메모리 절약됨. stable 정렬 방식

• 단점 : 자료 개수가 많아질수록 성능이 현저하게 떨어짐. ex) 자료가 100개라면 10000번 순회

구현

i를 한 번 순회할 때마다(안쪽 for문 모두 순회) 배열의 가장 큰 요소(숫자)가 마지막 인덱스로 밀려나므로 두 번째 for문 j 조건식에서 i를 빼면 불필요한 순회를 방지할 수 있다.

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

bubbleSort([10, 7, 9, 5, 1]); // [1, 5, 7, 9, 10]

i = 0, j 최대 3(arr.length - 1 - i)
========================
j = 0 : [7, 10, 9, 5, 1]
j = 1 : [7, 9, 10, 5, 1]
j = 2 : [7, 9, 5, 10, 1]
j = 3 : [7, 9, 5, 1, 10]

i = 1, j 최대 2
========================
j = 0 : [7, 9, 5, 1, 10]
j = 1 : [7, 5, 9, 1, 10]
i = 2 : [7, 5, 1, 9, 10]

i = 2, j 최대 1
========================
j = 0 : [5, 7, 1, 9, 10]
j = 1 : [5, 1, 7, 9, 10]

i = 3, j 최대 0
========================
j = 0 : [1, 5, 7, 9, 10]

배열 두 요소의 순서를 바꾸는 swap 코드는 아래와 동일하다.

if (arr[j] > arr[j + 1]) {
	// [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
	let temp = arr[j]
	arr[j] = arr[j + 1];
	arr[j + 1] = temp;
}

선택 정렬 | Selection Sort

[10, 7, 9, 5, 1] 배열을 선택 정렬하는 과정