[알고리즘] 버블, 선택, 삽입 정렬

Withlaw 2023. 10. 26. 01:23

1. Bubble Sort

-작은 데이터 셋이나, 데이터가 정렬이 거의 끝난 상태라는 걸 알고 있을 때 유용하다.

-원리: 정렬을 진행하면서 인접한 두 데이터를 비교하고 큰 값을 바꾸어 가며 가장 큰 값을 가장 끝으로 밀어낸다.

-최선: O(n) / 최악:O(n^2)

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;
}

——>O(n^2)

// Optimized

첫번째 for 문에서 루프의 반복 변수를 배열의 길이로 초기화 하는 이유: 버블 정렬의 특징상 한 번의 순회를 마치면 가장 큰 값은 무조건 끝으로 이동된다. 이들은 다시 정렬할 필요가 없기 때문에 다음 순회에서 j < i-1 을 통해 이미 정렬된 값은 검사하지 않는다. —>이를 통해 두번 째 for문의 실행횟수를 최적화할 수 있다.
swap이 있는 반복문에서 한 번이라도 swap이 실행되지 않으면 이미 정렬이 되어 있는 상태라고 볼 수 있다. 이번 순회에서 스왑이 한 차례도 일어나지 않았는데 다음 순회에서는 일어날까? 안일어난다. 그러니 이 경우 즉시 반복문을 탈출하도록 해주면 필요 없는 계산을 줄일 수 있다. —>이를 통해 첫번 째 for문의 실행횟수를 최적화할 수 있다.

function bubbleSort (arr) {
    const swap = (arr, idx1, idx2) => {
        [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    }
    let noSwaps = true;
    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);
                noSwaps = false;
            }
        }
        if (noSwaps) break; // 이런식의 최적화는 클래식한 방법이다.
    }
    return arr;
}

——>O(n)

2. Selection Sort

-버블 정렬처럼 대규모 데이터 셋을 다룰 땐 그 다지 효율적이지 않다. 버블 정렬보다 나은 점은 swap의 횟수가 현저히 적어 연산이 적게 들어간다 것.

-원리: 가장 작은 값을 선택해 차례로 정렬한다.(change). 버블 정렬은 가장 큰 값을 끝으로 밀어내고, 선택 정렬은 가장 작은 값을 앞으로 가져 온다.

-O(n^2)

function selectionSort(arr) {
  let count = 0;
  for (let i=0; i < arr.length; i++) {
    let swap = false;
    let min = i;
    for (let j=i+1; j < arr.length; j++) {
      if(arr[min] > arr[j]){
        min = j;
        swap = true;    // 여기서는 선택 정렬의 경우 실제 스왑이 일어났는지 체크하는 것은 전체 알고리즘의 시간복잡도에 큰 차이를 주지는 않는다
      }
      count++;
    }
    if(!swap) break;
    [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
}

——>O(n^2)

3. Insertion Sort

-카드 게임처럼 계속 새로운 데이터를 받아 정렬할 때 유용하다. 즉 이미 거의 정렬되어 있는 경우에 좋다. 기존에 정렬되어 있는 부분을 유지하면서 새로 받은 값을 어느 적당한 위치에 삽입할 지 확인하는 일만 한 번 수행하면 된다. 라이브 스트리밍 방식처럼 기존 정렬을 유지하면서 새 데이터가 들어올때마다 재정렬하는 작업에서 적합하다.

-원리: 정렬할 데이터를 선택하여 이미 앞에 정렬된 부분 사이에 삽입함. 카드 게임을 할 때 손에 든 카드를 정렬하는 방식과 유사. 새로운 카드를 가져왔을 때 기존의 카드들 가운데에 삽입함.

-최선: O(n) / 최악:O(n^2)

function insertionSort(arr) {
  for (let i=1; i<arr.length; i++){
    let current = arr[i];
    let j = i-1; 
    while ((j > -1) && (current < arr[j])) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = current;
  }
  return arr;
}

——>O(n^2)

셋 비교)

선택 정렬이 가장 사용될 확률이 적다. (최선의 상황에서도 시간복잡도가 n^2이다ㅠ)

거의 정렬이 완료된 상태에서 버블이나 삽입은 처음 순회를 돌고 이후에 효율적으로 중간에 검사(O(n))를 마치지만,

선택 정렬은 가장 작은 값을 찾기 위해 모든 순회를 꼭 완료해야 한다. 가장 작은 값이 어디에 있는지 모르니까. 이미 앞에 작은 값들이 정렬되어 있어도 이들을 다시 확인함.

무엇보다 셋 다 작은 규모의 데이터셋에서만 쓸모 있다.