[알고리즘] 버블 정렬

📌VISUALGO 사이트를 이용하면, 정렬 알고리즘을 시각적을 한 번에 이해하기 아주 좋다! 유용한 사이트

 

What is sorting?

Sorting is the process of rearranging the items in a collection (e.g. an array) so that the items are in some kind of order.
 
정렬을 수행하는 방법은 무수히 많다...
정렬 알고리즘이 무섭게 느껴지는 이유는 현존하는 유명 알고리즘을 15개나 떠올릴 수 있기 때문...!
 

Why do we need to learn this?

• Sorting is an incredibly common task, so it's good to know how it works.
  사용하는 언어에 내장된 정렬 메소드를 사용하고 있더라도, 거기에 어떤 알고리즘이 사용되는지를 이해한다면 각각을 사용하기 좋은 상황과 그렇지 않은 상황을 파악하는 데 도움이 된다.
• There are many different ways to sort things, and different techniques have their own advantages and disadvantages.

 

Objectives

• Implement bubble sort 버블 정렬
• Implement selection sort 선택 정렬
• Implement insertion sort 삽입 정렬
• Understand why it is important to learn these simpler sorting algorithms

 

JavaScript has a sort method...

하지만 항상 우리가 예상한 방식대로 작동하지는 않는다!
 
Like this:

 

---

BubbleSort

그닥 효율적이지 않고 흔히 쓰이지도 않는다.
그러나 알아두면 다른 알고리즘이 버블 정렬보다 더 나은 이유를 이해하는 데에도 도움이 된다.
 
A sorting algorithm where the largest values bubble up to the top!

 

Before we sort, we must swap!

Many sorting algorithms involve some type of swapping functionally ( e.g. swapping to numbers to put them in order )

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

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

 
 

BubbleSort 구현해보기

• Start looping from with a variable called i the end of the array towards the beginning
• Start an inner loop with a variable called j from the beginning until i - 1
• If arr[j] is treater than arr[j+1], swap those two values!
• Return the sorted array

바깥 루프가 감소하는 형태이고, 안쪽 루프에서 바깥 루프의 변수를 사용하는 게 핵심

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

 

BubbleSort 최적화

만약에 데이터가 거의 정렬이 된 상태거나 이미 정렬이 완료됐다면, 버블 정렬을 할 필요가 없다.
버블 정렬은 여전히 모든 항목을 하나하나 정렬하려고 하기 때문이다.
 
그렇다면 어떻게 해야할까?
루프가 마지막으로 실행됐을 때 swap이 일어났는지 안 일어났는지 체크하는 noSwaps라는 변수를 하나 만들어서,

이게 true라면 swap이 이루어지지 않고 루프에서 빠져나오게 해보자~!
왜냐, swap이 일어나지 않았다=정렬이 완료됐다 라는 의미이기 때문이다.

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