[Algorithm] Advanced Bubble Sort 알고리즘 Javascript

 

 

여러 자료를 규칙에 따라 나열하는 정렬 알고리즘은 다양한 종류가 있다. 삽입정렬, 버블정렬, 선택정렬, 쉘 정렬, 힙 정렬, 이진 병합 정렬, 퀵 정렬, 버킷 정렬 등 키값을 비교하는 방식에 따라 다양한 정렬이 있고, 각기 시간복잡도도 다르다. 

 

Bubble Sort 알고리즘

 

 

버블정렬?

버블 정렬은 각 위치와 인접한 오른쪽 값을 비교해서 데이터를 스왑(swap) 하는 정렬 방식이다. 첫번째 부터 시작한 비교와 스왑을 통해 마지막 위치에 가장 큰 값이 위치하게 된다.

정렬이 끝난 마지막 위치를 제외한 나머지 위치들의 데이터를 다시 순회하면서 정렬 작업을 반복하게 된다. 특정 요소가 오른쪽 값들과 비교하면서 뒤로 밀리는 모습이 거품같다고 해서 버블 정렬이라고 불린다.

버블 정렬의 시간복잡도는 O(n²) 다.

 

버블 정렬 알고리즘 순서

버블 정렬은 가장 첫번째 요소 부터 비교를 시작한다. 첫 요소인 50과 두번째 요소 61을 비교한다. 오름차순으로 정렬한다고 했을 때 두 수의 스왑은 일어나지 않는다.

 

두번째 정렬에서 61과 41을 비교하게 된다. 두 수는 스왑이 일어난다.

세번째 정렬이다. 61과 99는 스왑이 일어나지 않는다.

네번째 정렬이다. 99와 10은 스왑이 발생한다.

 

여기까지가 1번째 정렬 반복분의 한 과정이다. 이 과정이 배열의 길이만큼 반복이 진행된다. 두번째 정렬에서는 다시 50과 41을 비교하면서 시작할 것이고, 최종적으로는 가장 작은 수 10이 맨 앞에 위치하게 된다. 

 

 

Bubble Sort Algorithm 소스코드

 

Naive Algorithm

 

간단하게 알고리즘을 구성하면 아래와 같다. 배열 길이만큼 반복이 진행되고, 두번째 반복문에서 j번째 요소와 j+1번째 요소를 지속적으로 비교하면서 스와핑을 진행한다.

 

const bubbleSort = function (arr) {

	for(let i=0; i<arr.length; i++){
        for(let j=0; j<arr.length-i-1; j++){
            if(arr[j]>arr[j+1]){
                const temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
  };

 

여기서 새로운 문제가 발생한다. 버블정렬의 시간복잡도는 O(n²)이기 때문에 배열의 길이가 증가하면할 수록 연산횟수 또한 정비례하여 증가하게 된다. 위 예시 처럼 배열의 길이가 5개면 아무런 문제가 안되지만, 배열의 길이가 100,000만개가 넘어가는 경우 좀더 최적화된 알고리즘이 필요하다.

 

Advanced Bubble Sort Algorithm

버블 정렬 알고리즘 특성상 첫번째 요소 부터 두개의 요소를 지속적으로 비교하면서 배열 전체의 길이만큼 순회하게 된다. 이 때 스왑이 단 한번도 발생하지 않은 경우는 배열이 정렬되어 있는 것으로 볼 수 있다.

 

따라서 스왑이 발생했는지를 체크할 수 있는 변수를 생성한 후 스왑이 발생되는 경우 반복을 계속 진행하고 만약 스왑이 한번도 발생하지 않은 경우 바로 반복문을 탈출한다.

function bubbleSort(arr) {

    for(let i=0; i<arr.length; i++){
    	// 스왑 체크 초기값
        let swap = false;
        for(let j=0; j<arr.length-i-1; j++){
            
            if(arr[j]>arr[j+1]){
                const temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                
                // 스왑이 발생한 경우 체크
                swap = true;
            }
        }
        // 스왑이 한번도 일어나지 않은 경우 정렬이 되어 있는 상태
        if(!swap) break;
    }
    return arr;
  };

 

 

Experiment

테스트용 배열을 생성한다. 총 100,000개의 무작위로 shuffle 된 요소를 담은 배열이다.

const testArr = Array.from(Array(100000).keys()).map(()=>{return Math.round(Math.random() * 100000)});

 

 

case 1) Naive Algorithm 

기존 알고리즘으로 100,000개의 배열을 정렬할 때 필요한 연산횟수는 4,999,950,000번이다. 

➜  Algorithm_Immerse_Toy node 04_bubbleSort.js
4999950000
[
   0,  1,  3,  5,  6,  6,  6,  6,  6,  6,  7,  7,
   7,  8,  8,  8, 10, 10, 10, 10, 11, 12, 13, 13,
  14, 15, 16, 16, 17, 21, 24, 25, 26, 26, 26, 27,
  29, 29, 34, 34, 34, 35, 36, 38, 39, 39, 39, 39,
  40, 40, 41, 42, 42, 44, 45, 45, 48, 48, 50, 51,
  52, 55, 57, 57, 58, 59, 60, 62, 63, 63, 63, 63,
  64, 65, 66, 66, 67, 70, 72, 72, 73, 73, 74, 74,
  76, 77, 77, 79, 80, 80, 81, 81, 81, 82, 82, 85,
  86, 87, 87, 89,
  ... 99900 more items
]

 

case 2) Advanced Algorithm

개선된 알고리즘을 사용했을 때는 4,999,889,622번의 연산횟수가 필요하다. 기존 알고리즘 보다 60,378번 적은 연산횟수로 정렬이 가능하다. 

➜  Algorithm_Immerse_Toy node 04_bubbleSort.js
4999889622
[
   2,  2,  2,  2,  3,  4,  4,  5,  6,  6, 10, 11,
  12, 12, 13, 16, 17, 18, 20, 22, 23, 24, 25, 25,
  25, 26, 26, 26, 28, 28, 29, 29, 31, 31, 33, 36,
  37, 37, 37, 37, 38, 38, 39, 41, 41, 42, 43, 44,
  45, 46, 47, 47, 47, 47, 48, 52, 53, 54, 55, 57,
  58, 58, 59, 59, 60, 60, 63, 63, 63, 63, 64, 65,
  66, 67, 68, 69, 70, 71, 72, 72, 73, 75, 75, 76,
  77, 79, 79, 80, 80, 82, 82, 83, 84, 84, 84, 85,
  85, 90, 93, 96,
  ... 99900 more items
]

 

 

 

 

[Algorithm] Javascript BFS / DFS 알고리즘 문제 기초

 

[Algorithm] 시간복잡도 개선 부분집합 문제