JavaScript 알고리즘(2) 버블정렬(Bubble Sort)

 

 

Updated 10/30/22

 

알고리즘 두번째 시간😀

원리를 알아가니 퍼즐이 맞춰지는 느낌이다. 이렇게 하나하나 알아가보자!

자 그럼 버블정렬에 대해 알아가보자

 

 

---

버블 정렬(Selection Sort) 

정렬알고리즘 중 버블 정렬은 가장 큰 숫자를 선택해서 뒤로 보낸다.

옆 원소랑 비교해서 더 작은 값은 앞으로, 최대값을 뒤로 보내자! 

 

 

뒤죽박죽인 배열 내의 숫자들을 오름차순(1, 2, 3, ... 10)으로 정렬해보자

자, 준비물은 array, temp 다. 이 변수들 안에 숫자들을 담아 능력껏 줄세워보자.

 

첫번째 원소자리에는 1st - 10th 원소 검사해서 젤 큰 수를 맨뒤로 넣고,

두번째 원소자리에는 1st - 9th 원소 검사해서 젤 큰 수를 맨뒤로 넣고,

세번째 원소자리에는 1st - 8th 원소 검사해서 젤 큰 수를 맨뒤로 넣고,

 

1. 일단 for문으로 array 를 크게 한바퀴 돌면서, (1차 for문) 

2. 그 안에서 디페일하게 원소 검사 한바퀴 또 돌면서 최대값 찾고 (2차 for문)

3. 찾은 최대값과 현재 원소를 바꿔치기 해서 가장 큰 값을 맨 뒤로 이동시킨다.

 

let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];	//오름차순 정렬할 배열
let temp;	  //두 숫자(현재 값이랑 다음 값)을 바꿔치기하는 임시장소

// 1. 포문으로 배열을 검사한다.
for (let i = 0; i < 10; i++){
  // 2. 2중 포문으로 최대값을 맨 뒤로 옮기기
  for (let j = 0; j < 9-i; j++) { // 마지막 인덱스 9 - i만큼 뺀만큼만 검사한다.
    if (array[j] > array[j+1]){   // 현재 원소(array[j])가 바로 다음 원소보다 크면 
      // 두 원소 서로 스와핑
      temp = array[j];   	  // temp에 현재 원소(array[j])의 값을 넣어준다.
      array[j] = array[j+1]; 	  // 현재 원소(array[j])의 값을 다음 원소값으로 바꿔주고,
      array[j+1] = temp; 	  // temp, 즉 현재 원소 자리에는 다음 원소값으로 대체한다.
    }
  }
}

 

 

 

자, 이제 버블정렬을 함수로 만들어보자

function bubbleSort(arr){
    // 4, 3, 2, 1 ... 이런식으로 끝에서 → 앞으로 하나씩 검사
    for(var i = arr.length; i > 0; i--){ 
        let noSwaps = true;		// SWAP 여부를 알수있도록 true 로 둔다.
        
        // j 는 i 보다 - 1 적게 검사하자
        // 즉, i = 4 이면, j 는 3 까지만 검사
        for(var j = 0; j < i - 1; j++){
            if(arr[j] > arr[j+1]){
                //SWAP!
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;    
                noSwaps = false;	// SWAP 되면 false로 바뀐다
            }
        }
        
        if(noSwaps) break;		// 위에서 swap된 값이 하나도 없다면 for문 탈출!
    }
    return arr;
}

bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]);

 

 

콘솔로 찍어보면 바깥쪽의 for문을 한 바퀴씩 돌면서 비교하여 교체가 일어나는 것을 볼수있다.

 

 

 

 

버블정렬은 구현은 가장 쉽지만 가장 비효율적인 알고리즘이다. 

시작복잡도는 O(N^2)로 선택정렬과 같다. 하지만 구조적으로 들어가보면,    

선택정렬은 가장 작은 값을 골라 마지막에만 교체를 해주지만, 버블정렬은 매번 교체가 일어나기 때문에 비효율적이다.

 

 

 

 

ref: https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz