[TIL] 삽입정렬, 병합정렬 with Javascript

3. 삽입정렬(Insertion sort)

회전을 돌 때마다 정렬한 요소를 왼쪽에 쌓아가면서 각 요소를 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘. 손안의 카드를 정렬하는 방법과 유사하며, 매 회전마다 해당원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입한다. 키 값은 2번째 인덱스부터 시작되며 키 값이 자료의 길이만큼 이동하면 정렬이 완성됨.

 

1) 과정

i. 배열에서 두번째 요소(key)를 선택하여 루프를 시작

ii. 두번째 요소를 이전 요소와 비교하여 더 작은 경우 교체한다.

iii. 다음 요소로 계속 진행하며 왼쪽에 이미 정렬된 부분에서 반복문을 돌려 해당 요소가 있어야 할 위치에 삽입.

 

2) Big O

O(n)의 시간복잡도를 지닌다. 최악의 경우, 즉 배열이 완전히 역순으로 배치되어 있는 경우엔 O(n^2)이다.완전히 무작위인 배열에서는 성능이 떨어진다. 예를 들어 온라인에서 실시간 데이터를 받고있고 이를 모아서 정렬해야 한다면, 삽입정렬은 한 쪽에 정렬된 부분을 두고 한 번에 하나씩 요소들을 삽입하는 방식이기 때문에 적절할 수 있다. 사용할 수 있는 메모리가 제한적일 경우 사용시 이점이 있다.

 

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      // 인덱스 j부터 1까지 1씩 감소하며 반복
      if (arr[j] < arr[j - 1]) {
        // 한 칸씩 왼쪽으로 이동
        // swap
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      } else {
        // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        break;
      }
    }
  }
  return arr;
}

console.log(insertionSort([4, 3, 2, 1, 5, 20, 17]));

 

 

 

4. 병합정렬(Merge sort)

대표적인 분할정복(Divide and Conquer) 알고리즘으로 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 정렬된 하나의 리스트를 만든다. 보기 드문  Not in place Sorting 알고리즘이다.

 

1) 과정

i. 분할: 입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할한다. 즉, 리스트의 중간 지점에서 이루어진다.

ii. 정복: 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬한다. 이 과정은 입력리스트가 충분히 작아질 때까지 반복한다.

iii. 병합: 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합한다.

 

2) Big O

1개 항이 될 때까지 나눈 다음 합치기에 병합정렬에는 예외케이스는 없다. O(n logn)의 평균값을 가진다. log n은 'n 증가에 따르는 분할 수'이다.

 

function merge(arr1, arr2) {
  // 변수 2개에 빈 배열을 할당하고 마지막에 반환할 빈 배열을 만든다.
  const results = [];
  // i,j는 카운터로 가장 작은 값인 0(처음)부터 시작한다.
  let i = 0;
  let j = 0;

  // i와 j가 각 분할의 끝까지 도달할 때까지 계속된다.
  while (i < arr1.length && j < arr2.length) {
    // 1.첫번째 배열의 첫번째 값과 두번째 배열의 첫번째 값을 비교한다.
    if (arr2[j] > arr1[i]) {
      // 2. 더 큰 값을 취하여 results 배열에 푸쉬한다.
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }
  // 배열 하나를 완료하면 다른 배열의 남은 값을 모두 넣는다.
  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }

  return results;
}

// 병합정렬 구현코드
function mergeSort(arr) {
  // 배열의 길이가 1 혹은 0이 될때까지 재귀적으로 호출한다.
  if (arr.length <= 1) return arr;
  // 배열의 절반을 자르기 위해 mid 변수에 배열길이/2의 내림값을 저장한다.
  const mid = Math.floor(arr.length / 2);
  // 각 부분을 slice로 나누어주고 이들에게 mergeSort함수를 호출하는 것이다.
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

console.log(mergeSort([10, 36, 24, 76, 82, 73]));

 

출처: https://velog.io/@cookncoding/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-Stable-Sort-Inplace

[알고리즘 개념] Stable Sort &Inplace