[Algorithm 016] JS - Bubble Sort 버블정렬

✅ Bubble Sort (버블 정렬)

• 인접한 두 개의 데이터를 비교해 정렬
• 맨 앞의 데이터부터 비교 진행
• 회전 횟수 = 데이터 수 -1
  • comparisons = N - 1
• O(n²)
• 구현하기엔 쉽지만 효율성이 가장 떨어짐

정렬할 배열 : [ 8, 5, 6, 2, 4 ]
데이터 갯수 : 5개, 회전 수 :4회전
 
1회전) [ 8, 5, 6, 2, 4 ]
1swap : 5, 8, 6, 2, 4
2swap : 5, 6, 8, 2, 4
3swap : 5, 6, 2, 8, 4
4swap : 5, 6, 2, 4, 8

❗️ 결과 1회전 후 제일 큰 수가 뒤로간다.
❗️ 즉, 1회전마다 끝 값부터 정렬이 된다.

2회전) [ 5, 6, 2, 4, 8 ]
1swap : 5, 6, 2, 4, 8
2swap : 5, 2, 6, 4, 8
3swap : 5, 2, 4, 6, 8

3회전) [  5, 2, 4, 6, 8 ]
1swap : 2, 5, 4, 6, 8
2swap : 2, 4, 5, 6, 8

❗️ 우연히도 3회전에 이미 완벽히 정리된 배열이지만,
4회전을 돌며 비교를 시도하긴 한다.

4회전) [ 2, 4, 5, 6, 8 ]
1swap : 2, 4, 5, 6, 8

결과 [ 2, 4, 5, 6, 8 ]

 

 

 

Q. 주어진 배열을 버블 정렬로 정렬하기

[6, 5, 3, 2, 8]

 

 

 

A. 처음 접근 법

const bubbleSort = nums => {
  // 배열의 값을 순차적으로 돈다
  for( i = 0 ; i < nums.length ; i++){
  
    // 배열의 앞, 뒤 값을 비교하여
    // 앞의 값이 뒤의 값보다 크면
    if( nums[i] > nums[i + 1] ){
      // 해당 인덱스에 해당하는 값부터 1개 자르고,
      // 뒤의 값(큰 수)을 앞의 값(작은 수)과 바꾸어 추가한다. 
      nums.splice(i, 1, nums[i + 1], nums[i])
    }
  }
  // 이렇게 하면 1회전하고 끝
  return nums 
}

bubbleSort([6, 5, 3, 2, 8])  //[ 5, 3, 2, 6, 8 ]

하지만 이렇게 하면 1회전만 돌고 끝나버린다. 

 

 

 

B. 설명 참고해서 다시 풀기

const bubbleSort = nums => {
  let temp = 0;
  
  for( i = 0 ; i < nums.length ; i++){

    for ( j = 0 ; j <  nums.length -1 - i ;j++){

      if (nums[j + 1] < nums[j] ){
        temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;   
      }
      
    }
    
  }
  return nums 
}

bubbleSort([6, 5, 3, 2, 8]) // [2, 3, 5, 6, 8]

 

풀이

const bubbleSort = nums => {
  let temp = 0;

  // 배열의 값을 앞에서부터 순차적으로 돌겠다.
  for( i = 0 ; i < nums.length ; i++){

    // 끝 까지 돌았어도, 1번 더 돌리겠다!
    for ( j = 0 ; j <  nums.length -1 - i ;j++){

      // 두 수를 비교해서 뒤의 수가 앞의 수보다 작으면
      if (nums[j + 1] < nums[j] ){
      
        temp = nums[j]; // 앞(작은) 수 값을 뒷(큰) 수로 변경
        nums[j] = nums[j + 1]; // 앞(작은) 수 값을 뒷(큰) 수로 변경
        nums[j + 1] = temp; // 뒷(큰) 수 값을, temp값으로 변경 (nums[i]값은 이미 변경되었기 때문)
        
      }
    }
  }
  return nums 
}

bubbleSort([6, 5, 3, 2, 8]) // [2, 3, 5, 6, 8]

 

for ( j = 0 ; j <  nums.length -1 - i ;j++){ } 의 의미

• 버블 정렬은 매 1회전마다 끝 자리(큰 수)부터 순차적으로 정렬된다.
  고로 다음 회전은 정렬이 완료된 값의 갯수를 뺀 횟수만큼만 돌겠다.
• 데이터가 5개일 경우
  •  1회전때는 4번
  • 2회전 때는 3번
  • 3회전 때는 2번
  • 4회전 때는 1번

 

// 위 함수의 loop별 결과값
'1회전 1번: 5,6,3,2,8'
'1회전 2번: 5,3,6,2,8'
'1회전 3번: 5,3,2,6,8'
'1회전 4번: 5,3,2,6,8'

'2회전 1번: 3,5,2,6,8'
'2회전 2번: 3,2,5,6,8'
'2회전 3번: 3,2,5,6,8'

'3회전 1번: 2,3,5,6,8'
'3회전 2번: 2,3,5,6,8'

'4회전 1번: 2,3,5,6,8'

 

 

C. 추가

• 처음부터 순차적으로 정렬이 되어있는 배열의 경우

[1, 2, 3, 4 ,5]

const bubbleSort = nums => {
  let temp;
  for( i = 0 ; i < nums.length ; i++){
    for ( j = 0 ; j <  nums.length -1 - i ;j++){
    
      if (nums[j + 1] < nums[j] ){
        temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
     
    }
    
    // 1회전 동안 temp의 값이 한 번도 정의되지 않을 경우, 바로 for문을 빠져나온다.
    if (!temp) {
      break;
    }
  }
  
  return nums 
}

bubbleSort([1, 2, 3, 4 ,5]) // [1, 2, 3, 4 ,5]

// 위 함수의 loop별 결과값
'1회전 1번: 1,2,3,4,5'
'1회전 2번: 1,2,3,4,5'
'1회전 3번: 1,2,3,4,5'
'1회전 4번: 1,2,3,4,5'

 

• 배열 정렬이 완벽해진 순간부터 함수를 빠져나오고, 더 이상 실행 시키지 않게하는 방법

const bubbleSort = nums => {
  let temp, swaps;
  for( i = 0 ; i < nums.length ; i++){
    swaps = false
    
    for ( j = 0 ; j <  nums.length -1 - i ;j++){
    
      if (nums[j + 1] < nums[j] ){
        temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
        swaps = true
      }
     
    }
    
    // 앞의 값이 뒤의 값보다 큰 케이스가 없다면 swaps = false
    // swaps = false일 경우 함수 종료
    if (!swaps) {
      break;
    }
  }
  
  return nums 
}

bubbleSort([2, 3, 1, 4 ,5])  // [ 1, 2, 3, 4, 5 ]

// 위 함수의 loop별 결과값
'1회전 1번: 2,3,1,4,5'
'1회전 2번: 2,1,3,4,5'
'1회전 3번: 2,1,3,4,5'
'1회전 4번: 2,1,3,4,5'

'2회전 1번: 1,2,3,4,5'
'2회전 2번: 1,2,3,4,5'
'2회전 3번: 1,2,3,4,5'

'3회전 1번: 1,2,3,4,5'
'3회전 2번: 1,2,3,4,5'

//종료 (4회전은 하지 않는다.)

   

 

참고

노마드코더 - 어? 재밌네? 정렬 알고리즘, 한방에 이해하기!

엔지니어대한민국 - [자료구조 알고리즘] 버블정렬(Bubble Sort) 자바로 구현하기

zerocho -버블(거품) 정렬(bubble sort)