Bubble Sort 정리

목표

• bubbleSort 알고리즘 이해
• 자바스크립트로 bubbleSort 구현
• bubbleSort 특징 이해
• bubbleSort 알고리즘의 시간복잡도 이해

BubbleSort 알고리즘의 개념

• 서로 인접한 두 원소를 비교하여 크기순으로 정렬한다.
  • 첫번째 원소와 두번째 원소를, 두번쨰 원소와 세번째 원소를,... 이런 식으로 마지막-1 번째 원소와 마지막 원소를 반복 비교하며 크기순으로 정렬 한다.
  • 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동한다. 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다. 이렇게 회전이 늘어날 수록 제외되는 데이터가 늘어난다.

 

• 선택 정렬과 기본개념이 유사하다.

BubbleSort 예시

https://needjarvis.tistory.com/582

BubbleSort 자바스크립트 코드

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 반복문으로 앞,뒤 요소들을 비교한다.
  // 앞요소가 뒤요소보다 크면 두 요소의 위치를 바꾼다.
  // 결과적으로 가장 큰 요소가 배열의 마지막으로 밀려난다. 
  // 이때 어떤 요소도 위치가 바뀌지 않았으면 이미 정렬되어있는 상태이다.-> 바로 끝낸다.
  // 위 과정을 반복하여 두번째 큰요소, 세번째 큰 요소,... 큰 요소들이 순서대로 끝으로 밀려난다.
  // 이를 배열의 크기만큼 반복한다.

  //가장 큰 원소는 가장 뒤로 밀려난다.
  //가장 뒤로 밀려난 원소는 작업에서 제외시킨다. 
  for(let i = arr.length-1;i>0;i--){
    //1회전이 끝날때마다 count 초기화
    let count = 0

    for(j=0;j<i;j++){
      if(arr[j]>arr[j+1]){
      //arr는 reference type이기 때문에 구조분해 할당으로 앞,뒤 요소를 교환할 수 있다.
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        //하나라도 바뀌면 count를 증가시킨다.
        count ++
      }

    }
    //바뀐게 없다면 이미 정렬된 상태이므로 작업을 마친다.
    if(count===0)break
  }
  return arr
  };

BubbleSort 특징

• 장점
  • 구현이 간단

 

• 단점
  • 순서에 맞지 않은 요소를 인접한 요소와 교환
  • 한 요소를 뒤로 보내기 위해 모든 요소들과 비교하며 교환한다.
  • 특정 요소가 최종 정렬 위치에 있더라도 교환되는 일이 발생한다.

 

• 일반적으로 자료의 교환작업이 이동작업보다 복잡하기 때문에 버블 정렬은 단순하지만 거의 쓰이지 않는다.

 

시간복잡도

이중반복문이므로 O(n^2)이다.

 

최악의 경우는 배열이 내림차순으로 정렬되어 있는 경우이다. 

 

최상의 경우는 배열이 이미 오름차순으로 정렬되어 있어서 자료의 이동이 발생하지 않는 경우이다.

 

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

• 단순, 비효율 : 삽입정렬, 선택정렬, 버블정렬
• 복잡, 효울 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬