[알고리즘 with JS] 버블 정렬, 선택 정렬, 삽입 정렬에 대하여

 

버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보겠습니다.

 

 

🧑🏻‍💻 정렬이 무엇인가? 

정렬은 항목이 일종의 순서가 되도록 컬렉션(예: 배열)의 항목을 재정렬하는 프로세스입니다. 

 

📌 정렬을 왜 알아야 하는가?

 

- 정렬은 매우 일반적인 작업이므로 작동 방식을 아는 것이 좋습니다.

- 물건을 분류하는 방법에는 여러 가지가 있으며, 기술마다 장단점이 있습니다.

 

 

⭐️ 버블 정렬 (Bubble Sort)

 

 

버블 정렬은 잘 사용되지 않고 엄청 효율적이지는 않습니다. 하지만 어떻게 사용하는지 알면 재미있는 정렬 방식입니다.

 

버블 정렬의 개념은 배열을 가장 작은 숫자에서 가장 큰 숫자 순으로, 즉 오름차순으로 정렬한다면 더 큰 숫자가 한 번에 하나씩 뒤로 이동한다는 것입니다. 

 

 

 

 

📚 버블 정렬 예시

 

- 배열의 끝인 i라는 변수에서 처음부터 반복을 시작합니다.

- 처음부터 i-1까지 j라는 변수로 내부 루프를 시작합니다.

- arr[j]가 arr [j+1] 보다 크면 이 두 값을 바꿔줍니다.

- 정렬된 배열을 반환합니다.

 

// O(N^2)
const bubbleSort1 = (arr) => {
    for(let i = arr.length;  i > 0; i--) {
        for(let j = 0; j < i-1; j++) {
            console.log(arr, arr[j], arr[j+1]);
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
};

// ES 2015 ver O(N^2)
const bubbleSort2 = (arr) => {
    for(let i = arr.length;  i > 0; i--) {
        for(let j = 0; j < i-1; j++) {
            console.log(arr, arr[j], arr[j+1]);
            if(arr[j] > arr[j+1]){
           [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
};


// 최적화 ver  O(N2)
const bubbleSort3 = (arr) => {
    let noSwap;
    for(let i = arr.length;  i > 0; i--) {
        noSwap = true;
        for(let j = 0; j < i-1; j++) {
            console.log(arr, arr[j], arr[j+1]);
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                noSwap = false;
            }
        }
        if(noSwap) break;
    }
    return arr;
};

 

⭐️ 선택 정렬 (Selection Sort)

 

 

버블 정렬과 유사하지만 큰 값을 정렬된 위치에 먼저 배치하는 대신 작은 값을 정렬된 위치에 배치합니다.

( 큰 값을 배열 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열합니다. ) 

 

버블 정렬과 마찬가지로 처음부터 끝까지 움직이지만, 실제 정렬된 데이터는 처음부터 누적되고 있습니다. 

 

 

 

📚 선택 정렬 예시

 

- 지금까지 본 가장 작은 값으로 첫 번째 요소를 저장합니다.

- 더 작은 숫자를 찾을 때까지 이 항목을 배열의 다음 항목과 비교합니다.

- 더 작은 숫자가 발견되면 더 작은 숫자를 새로운 "최솟값"으로 지정하고 array 끝까지 계속합니다.

- "최소값"이 처음에 시작한 값(index)이 아닌 경우 두 값을 서로 바꿉니다.

- 배열이 정렬될 때까지 다음 요소에 대해 이 작업을 반복합니다.

 

// O(N^2)
const selectionSort = (arr) => {
  for (var i = 0; i < arr.length; i++) {
    var lowest = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j;
      }
    }
    if (i !== lowest) {
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }
  }
  return arr;
};

console.log(selectionSort([34, 22, 10, 19, 17]));

 

⭐️ 삽입 정렬 (Insertion Sort) 

 

한 번에 하나를 취해서 올바른 위치에 삽입하는 정렬입니다.

 

 

📚 삽입 정렬 예시

 

- 배열에서 두 번째 요소를 선택하여 시작

- 이제 두 번째 요소를 이전 요소와 비교하고 필요한 경우 교환합니다.

- 다음 요소로 계속 진행하고 순서가 잘못된 경우 정렬된 부분(예: 왼쪽)을 반복하여 올바른 위치에 요소를 배치합니다.

- 배열이 정렬될 때까지 반복합니다.

 

/*
    Insertion Sort
*/

const insertionSort = (arr) => {
    for (var i = 1; i < arr.length; i++) {
        var currentVal = arr[i];
        for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j + 1] = arr[j];
        }
    arr[j + 1] = currentVal;
}
return arr;
};

console.log(insertionSort([2, 1, 9, 76, 4]));

 

 

⭐️ 요약

 

 

🏷️ 사진 출처

https://www.chanstory.dev/blog/post/17

https://hanhyx.tistory.com/38

https://m.blog.naver.com/jsky10503/221249976761

https://sylagape1231.tistory.com/17