버블 정렬

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
둔 다 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다.
n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 정렬된다.

예를 들어 5,1,6,2,4,3을 오름차순으로 정렬한다고 가정해보자.
먼저 5, 1을 비교하여 1은 5보다 작기 때문에 위치를 바꿔준다.
다음 5, 6을 비교하하는데 올바른 순서이기 때문에 넘어간다.
위의 과정을 모든 요소가 정렬 될 때까지 반복한다.

시간 복잡도

• worst case : O(n^2)
  • 정렬이 하나도 안되어있을 때
• best case : O(n)
  • 이미 정렬이 되어있을 때

구현 알고리즘

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

선택 정렬

배열 안의 자료 중 가장 작은수(또는 가장 큰 수)를 찾아 첫 번째 위치(또는 마지막 위치)의 수와 교환하는 방식으로 정렬한다.
교환 횟수를 최소화하는 반면에 각 자료를 비교하는 횟수는 증가한다.

버블 정렬 예와 같이 5,1,6,2,4,3을 정렬한다고 하면
0번째 인덱스 값인 5를 기준으로 시작한다.
5를 [1,6,2,4,3]과 비교하여 최솟값을 찾는다.
1(가장 작은수)을 5의 위치와 교환한다.
1을 제외한 5,6,2,4,3에서 최솟값을 찾는다.
2(가장 작은수)를 5의 위치와 교환한다.

시간 복잡도

• worst case : O(n^2)
  • 정렬이 하나도 안되어있을 때
• best case : O(n^2)
  • 이미 정렬이 되어있을 때
  • 매 번 정해진 자리에 올 수 있는 최솟값을 찾아야하기 때문에 n^2가 된다. 매우 비효율적인 정렬

구현 알고리즘

function selectionSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      let swap = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = swap;
    }
    console.log(`${i}회전: ${array}`);
} 
  return arr;
}

삽입 정렬

정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방식이다.

5, 1, 6, 2, 4, 3을 삽입 정렬로 정렬한다면
배열의 첫 번째 자리는 이미 정렬된 부분이라 가정한다.
5를 제외한 1,6,2,4,3은 정렬되지 않은 부분이고, 여기서 처음에 위치한 1은 5보다 작기 때문에 1을 5앞에 넣는다.
정렬되지 않은 부분 6,2,4,3에서 6은 5보다 크므로 넘어간다.
2,4,3에서 2를 정렬된 1,5,6과 비교하여 1,5사이에 넣는다.

시간 복잡도

• worst case : O(n^2)
  • 정렬이 하나도 안되어있을 때
• best case : O(n)
  • 이미 정렬이 되어있을 때

구현 알고리즘

function insertionSort (array) {
  //정렬할 배열을 순회한다.
  for (let i = 1; i < array.length; i++) {
    //현재 비교할 순자를 뽑는다.
    let cur = array[i];
    //왼쪽 부분(정렬된 부분)
    let left = i - 1;
    //왼쪽 부분 숫자들과 현재 숫자를 계속 비교
    while (left >= 0 && array[left] > cur) {
      array[left + 1] = array[left];
      array[left] = cur;
      cur = array[left];
      left--;
    }
  }
  return array;
}

합병 정렬

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.

3,5,2,6,4,1을 반으로 쪼갠다.
[3,5,2][6,4,1] 각 배열을 다시 반으로 쪼갠다.
원소가 한 개가 될 때까지 쪼개다가 원소를 정렬해가면서 병합한다.

시간 복잡도

• O(nlogN)

구현 알고리즘

function mergeSort (array) {
  if (array.length < 2) {
    return array;
  }
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);
  
  return merge(mergeSort(left), mergeSort(right));
  
  //병합을 위한 함수
  function merge (left, right) {
    const resultArray = [];
    let leftIndex = 0;
    let rightIndex = 0;
    while (leftIndex < left.length && rightIndex < right.length) {
      if (left[leftIndex] < right[rightIndex]) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
      } else {
        resultArray.push(right[rightIndex]);
        rightIndex++;
      }
    }
    return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
  }
}

• 코드 출처: [Code Playground]