알고리즘

버블정렬 알고리즘 분석하기 (JavaScript)

2024년 08월 09일 11:39

안녕하세요 NekoNynagYee입니다!!

이번에는 알고리즘을 공부하다보면 기초적으로 나오는 알고리즘 중 하나인 버블정렬 알고리즘에 대해서 알아보려합니다.

1. 버블정렬(Bubble Sort) 알고리즘이 뭔가요?

이름에서 알 수 있다시피 배열의 요소를 거품처럼 서로 비교하고 교환해가면서 정렬 하는 방식입니다.

즉, 서로 인접하는 두 요소를 비교후 오름차순이나 내림차순으로 정렬하는 방식입니다.

2. 기본 구조는 어떻게 생겼나요?

오름차순으로 정렬한다는 가정하에 두 인접하는 요소를 비교하여 더 큰 숫자가 한번에 한칸씩 뒤로 이동하는 구조입니다.

코드로 설명하자면 i번째 요소와 j번째 요소와 비교 했을 때 j번째 요소가 더 크면 j번째 요소를 한칸 뒤로 밀어서 그 다음 원소와 비교하고 계속 이 행동을 반복하여 하나의 정렬된 배열을 완성시키는 것입니다.

function bubbleSort(list) {
  for (let i = 0; i < list.length; i++) {
    for (let j = 1; j < list.length - i; j++) {
      if (list[j - 1] > list[j]) {
        [list[j - 1], list[j]] = [list[j], list[j - 1]];
      }
    }
  }
  return list;
}
 
console.log(bubbleSort([1, 6, 2, 7, 4, 3, 8, 5]));

위에는 제가 짠 알고리즘 코드입니다. 사람들마다 조금씩 방식이 다르겠지만 아마 대부분 전체적인 구조는 비슷 할 것으로 예상됩니다.

이렇게 봐서 이해하기 힘드실 수도 있으니 밑에 동작 과정을 적어보겠습니다.

// 1. i = 0, j = 1 ===> [1, 6, 2, 7, 4, 3, 8, 5]
// 2. i = 0, j = 2 ===> [1, 2, 6, 7, 4, 3, 8, 5]
// 3. i = 0, j = 3 ===> [1, 2, 6, 7, 4, 3, 8, 5]
// 4. i = 0, j = 4 ===> [1, 2, 6, 4, 7, 3, 8, 5]
// 5. i = 0, j = 5 ===> [1, 2, 6, 4, 3, 7, 8, 5]
// 6. i = 0, j = 6 ===> [1, 2, 6, 4, 3, 7, 8, 5]
// 7. i = 0, j = 7 ===> [1, 2, 6, 4, 3, 7, 5, 8]
 
// 8. i = 1, j = 1 ===> [1, 2, 6, 4, 3, 7, 5, 8]
// 9. i = 1, j = 2 ===> [1, 2, 6, 4, 3, 7, 5, 8]
//10. i = 1, j = 3 ===> [1, 2, 4, 6, 3, 7, 5, 8]
//11. i = 1, j = 4 ===> [1, 2, 4, 3, 6, 7, 5, 8]
//12. i = 1, j = 5 ===> [1, 2, 4, 3, 6, 7, 5, 8]
//13. i = 1, j = 6 ===> [1, 2, 4, 3, 6, 5, 7, 8]
 
//14. i = 2, j = 1 ===> [1, 2, 4, 3, 6, 5, 7, 8]
//15. i = 2, j = 2 ===> [1, 2, 4, 3, 6, 5, 7, 8]
//16. i = 2, j = 3 ===> [1, 2, 3, 4, 6, 5, 7, 8]
//17. i = 2, j = 4 ===> [1, 2, 3, 4, 6, 5, 7, 8]
//18. i = 2, j = 5 ===> [1, 2, 3, 4, 5, 6, 7, 8]