버블 정렬

Doozuu·2023년 2월 6일

프로그래머스

알고리즘&자료구조 (JS)

목록 보기

7/25

📌 정렬이란 무엇인가?

collection의 항목을 재배열하는 과정을 의미한다.

ex) 배열 안의 숫자들을 오름차순/내림차순으로 정렬, 문자를 알파벳순으로 정렬, 영화 데이터를 개봉 연도순으로 정렬하는 등

📌 정렬 알고리즘을 왜 배워야 하는가?

정렬이 프로그래밍에서 매우 흔하게 사용되기 때문이다.
정렬할 수 있는 방법이 굉장히 다양하고, 각각 다른 장단점을 갖고 있기 때문이다.

입력값에 따라 어떤 알고리즘이 더 효율적인지 보여주는 사이트
https://www.toptal.com/developers/sorting-algorithms

직접 들어가서 살펴보면 다음과 같은 특징들이 있다.

입력값이 랜덤한 경우에는 Heap이 가장 효율적이고, selection과 bubble은 비효율적이다.
입력값이 거의 정렬된 경우에는 Insertion과 bubble이 효율적이고, selection은 매우 비효율적이다.
입력값이 거꾸로 정렬된 경우에는 Heap이 가장 효율적이고, Selection과 bubble은 비효율적이다.
입력값에 몇몇 Unique한 값들이 있는 경우에는 Quick3, Insertion, Heap이 효율적이고, Selection과 bubble은 비효율적이다.

🔗 자바스크립트 정렬 메서드인 sort( )의 작동원리

sort( )의 기본 정렬 순서는 문자열 유니코드에 따른다.

즉, 숫자도 문자열로 바꾼 후에 정해진 유니코드에 따라 정렬한다는 뜻으로, 숫자가 담긴 배열을 sort( ) 해주면 오름차순으로 정렬되지 않고 뒤죽박죽으로 정렬된다.

그래서 sort((a,b) => a - b) 등을 이용해 정렬해준다.
다양하게 활용이 가능한데, 만약 문자열이 담긴 배열을 입력받아서 문자열의 길이에 따라 오름차순으로 정렬하고 싶다면, sort((a,b) => a.length - b.length)로 정렬할 수 있다.

📌 버블 정렬(Bubble sort)

배열에 있는 숫자를 오름차순으로 정렬하는 경우, 수를 앞에서 부터 2개씩 비교해서 더 큰 숫자가 뒤로 이동하도록 자리를 바꾼다. -> 이를 교환(swap)이라고 부른다.
전부 정렬될 때까지 비교하고 교환하는 과정을 반복한다.

별로 효율적이지 않고 잘 사용되지도 않는다.
시간 복잡도 :
중첩 루프가 있기 때문에 일반적으로는 O(n^2)이다.
그러나 거의 정렬된 데이터가 주어질 때, 최적화한 코드(noSwap)를 사용하면 O(1) 혹은 O(n)이 된다.

버블 정렬 과정 애니메이션으로 보기
https://visualgo.net/en/sorting?slide=4-1

swap 방법

idx1 과 idx2 의 위치를 바꾸는 코드

function swap(arr, idx1, idx2){
	var temp = arr[idx1];
    arr[idx1] = arr[ix2];
    arr[idx2] = temp;
}

버블 정렬 과정

// 1번째 정렬
[`5`,`3`,4,1,2]
[3,`5`,`4`,1,2]
[3,4,`5`,`1`,2]
[3,4,1,`5`,`2`]
[3,4,1,2,5]
// 2번째 정렬
[`3`,`4`,1,2,5]
[3,`4`,`1`,2,5]
[3,1,`4`,`2`,5]
[3,1,2,4,5]
// 3번째 정렬
[`3`,`1`,2,4,5]
[1,`3`,`2`,4,5]
[1,2,3,4,5]

답 : [1,2,3,4,5]

예제

배열에 주어진 숫자들을 오름차순으로 정렬하기

버블 정렬 - naive한 버전

모든 요소를 전부 비교하기

swap을 할수록 맨 뒤에 있는 요소들부터 차곡차곡 정렬이 되기 때문에 이미 정렬된 값들은 다시 비교할 필요가 없는데 계속 모든 요소를 비교한다.
(정렬이 진행될수록 비교 횟수가 점점 줄어들어야 하는데 똑같아서 비효율적이다.)

function bubbleSort(arr){
  for(var i = 0; i < arr.length; i++){
    for(var j = 0; j < arr.length; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

버블 정렬 - 조금 개선된 버전

이미 정렬된 요소는 다시 비교하지 말기

i : 배열의 처음이 아닌 맨 끝부터 시작해서 하나씩 줄어들게 함.
j : i 를 이용해 정렬이 진행될수록 비교 횟수가 줄어들게 함.
(i가 감소함에 따라 j도 감소)

예를 들어 배열의 길이가 4일 때,
첫 번째 시행에서는 i = 4 이므로 j = 0,1,2,3 까지 시행되고, 두 번째 시행에서는 i = 3 이므로 j = 0,1,2 까지, 세 번째 시행에서는 i = 2이므로 j = 0,1까지 시행된다.
이렇게 해주면 이전 방식에 비교해 시행횟수가 많이 줄어들게 된다.

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

똑같은 풀이지만 ES2015 버전으로 풀면 아래처럼 풀 수 있다.
(swap 방식이 조금 다름.)

// ES2015 Version
function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  };

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

버블 정렬 - 최적화된 버전 ⭐️

거의 정렬된 데이터가 주어진 경우에 버블 정렬을 하면, 정렬이 완료되었음에도 계속 무의미한 정렬을 반복하는 것을 볼 수 있다.
이유 : 정렬이 중간에 완료되면 시행을 멈추어도 되는데 이를 멈출 수 있는 브레이크가 없기 때문.

무의미한 정렬을 막기 위해서는 반복문이 마지막으로 실행됐을 때 교환이 일어났는지 확인해주면 된다.
-> 교환이 일어나지 않았다는 것은 이미 정렬이 완료되었다는 것을 의미하기 때문에 반복문을 빠져나오면 된다.

function bubbleSort(arr){
  let noSwap; // swap 여부를 체크하기 위한 변수 설정
  for(var i = arr.length; i > 0; i--){
    noSwap = true; // 기본적으로 true로 세팅
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;    
        noSwap = false; // swap이 진행되면 false로 업데이트
      }
    }
    if(noSwap) break; 
    // noSwap이 true면 정렬이 완료되어 swap이 일어나지 않았다는 것이므로 실행 중지
  }
  return arr;
}