[코딩 테스트] 버블 정렬 및 버블 정렬 최적화 with JavaScript

Introduction

버블 정렬은 유명한 정렬 방법이라 어느정도 알고 계신 분들이 있을 실 것이다. 버블 정렬 하는 방법은 여러가지가 있지만 최적화 하는 방법이 존재합니다. 이는 코딩 테스트의 단골 문제로 유명합니다.

 

버블 정렬 (Bubble Sort)

버블 정렬, 영어로는 Bubble Sort 라고 알려져있습니다. 거품이 올라가는 모양과 닮았다고 해서 붙여진 이름입니다.

버블 정렬 이미지

유명한 버블 Sort GIF

1. 첫 번째와 두 번째 데이터를 비교합니다
2. 첫 번째가 두 번째 보다 크다면 Swap을 진행합니다.
3. 모든 Array 를 돌때 까지 계속합니다.

생략된 부분이 많아 보이지만, 이미지만 보고도 쉽게 이해 할 수 있습니다.

추가적으로 버블 정렬은 다른 정렬보다 느리지만 메모리를 적게 사용한다는 장점이 있습니다.

Code

버블 정렬의 장점은 구현 방법이 쉽다는 것입니다. 단순히 두개의 Loop 만을 호출 하면 됩니다.

function bubbleSort(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]) {
      	isSwapped = true
        // Swap
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
    	}  
    }
  }
}

const arr = [2, 9, 6, 5, 8];
bubbleSort(arr);

 

최적화된 버블 정렬 (Optimized Bubble Sort)

만약에 중간에서 이미 정렬이 완료되었다면, 더 이상 정렬을 진행할 필요가 없습니다.

그래서 정렬이 완료됐다고 판단되면 `break` 구문을 사용해서 Loop를 멈춰주면 됩니다.

위의 예제 코드를 수정해보면 다음과 같습니다.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
  	let isSwapped = false
  	for (let j = 0; j < arr.length - i - 1; j++) {
    	// 현재 값이 다음 값 보다 크다면
    	if (arr[j] > arr[j + 1]) {
      	isSwapped = true
        // Swap
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
    	}  
    }
   
    // Swap이 일어나지 않음
    if(!isSwapped) break
  }
}

const arr = [2, 9, 6, 5, 8];
bubbleSort(arr);

만약 Swap 과정이 일어 나지 않았다면, Outer Loop 를 빠져나오면 됩니다.

Reference

https://www.computersciencebytes.com/sorting-algorithms/bubble-sort/

Bubble Sort - COMPUTER SCIENCE BYTES

https://learn.coderslang.com/0037-javascript-optimized-bubble-sort.-coctail-sort/

Optimized bubble sort in JavaScript. Cocktail sort

https://learnersbucket.com/examples/algorithms/bubble-sort-algorithm-in-javascript/

Bubble sort algorithm in javascript

https://window6kim.tistory.com/41#%EB%B-%--%EB%B-%--%--%EC%A-%--%EB%A-%AC%---Bubble%--Sort-