거품 정렬 (Bubble Sort)

Aaron·2020년 10월 26일
Bubble Sort거품 정렬알고리즘정렬정렬 알고리즘
0

알고리즘

목록 보기
2/6
post-thumbnail

정의

  • 인접한 두 원소를 비교하여 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘
  • 정렬 과정에서 원소의 이동이 거품이 수면 위로 올라오는 것과 같다 하여 bubble sort로 이름 지어짐

과정 (오름차순)

  • 맨 앞에서부터 맨 뒤까지 비교하며 정렬하고, 그 결과 맨 뒤는 제일 큰 값이 되니까 앞으로의 정렬에서 제외 => 정렬이 끝날 때까지 반복

코드 (JS)

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {        // 앞으로의 정렬에서 제외될 요소의 개수를 0부터 하나씩 늘려감
    for (let j = 1; j < arr.length - i; j++) {  // 제외된 요소들은 빼고 처음부터 끝까지 인접한 두 요소를 비교하여 교환하는 로직
      let temp;
      if (arr[j - 1] > arr[j]) {
        temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  console.log(arr);
};

시간 복잡도

  • 비교 횟수
    • 최악, 평균, 최선 모두: (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2
  • 교환 횟수
    • 최악: 한 번의 교환을 위해 3번의 이동(swap 함수의 작업)이 필요하므로
      비교 횟수 * 3 = 3n(n-1)이 교환 횟수
    • 최선: 교환 일어나지 않음
  • 따라서 T(n) = O(n^2)
  • 매개변수가 정렬이 되었는지와 상관없이 무조건 비교하므로 최악, 평균, 최선 모두 동일

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬되므로 O(n)

장점

단점

  • 최악, 평균, 최선 모두 시간 복잡도가 O(n^2)으로 매우 비효율적이다
  • 정렬되지 않은 원소가 자기 자리를 찾아가는 과정에서 교환(swap)연산이 많이 일어난다

마무리

정렬 알고리즘 중 가장 직관적이면서 비효율적인 정렬 방식으로
선택 정렬(Selection Sort)과 기본 개념이 유사하다

참조

profile
Aaron
Maker를 지향하는 웹 개발자입니다.
이전 포스트

시간 복잡도 vs 공간 복잡도

다음 포스트

안정 정렬 vs 불안정 정렬(feat. 제자리 정렬)

0개의 댓글