JavaScript_Basic 지식으로 여러 정렬 알고리즘을 간단하게 구현

정렬 알고리즘 구현

저는 JS 실력이 부족해서 JAVA, C와 유사한 방법을 사용하여 JavaScript 정렬 알고리즘을 작성합니다.

그리고 여기서는 알고리즘 원리에 대해서는 다루지 않고 코드 구현에 대해서만 이야기하겠습니다. 버그가 있을 수 있습니다. 지침을 얻기 위해 누구나 블로그에 댓글을 달 수 있습니다.
삽입정렬

삽입 정렬의 알고리즘 설명은 간단하고 직관적인 정렬 알고리즘입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 추가 공간만 사용하는 정렬)이 사용되므로 스캔 과정에서 뒤에서 앞으로 반복적이고 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.

구현 코드는 다음과 같습니다.

function insertSort(arr) {
  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 1, len = arr.length; i < len; i ++) {
    var stand = arr[i];
    for (var j = i - 1; j >= 0; j --) {
      if (arr[j] > stand) {
        arr[j + 1] = arr[j];
      } else {
        arr[j + 1] = stand;
        break;
      }
    }
  }

  return arr;
}

시간 복잡도는 O(n^2)

물론, 검색과 치환의 위치 알고리즘을 이진 검색으로 변경하는 등 이 알고리즘을 최적화할 여지는 있습니다.
버블 정렬

고전적인 정렬 알고리즘, 버블 정렬을 하면 마음이 아픕니다. 학부시절 버블정렬 알고리즘 개선에 대한 필수 논문을 작성했는데, 그 결과 논문 작성을 마친 후에도 버블정렬 알고리즘을 완벽하게 구현하지 못해서 너무 당황스러웠습니다.

  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 0; i < len; i ++) {
    for (var j = 0; j < len - i - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }

  return arr;
}

시간 복잡도는 O(n^2)
빠른 정렬

매우 고전적인 정렬 알고리즘은 주로 세 단계로 나뉩니다.

1. 시퀀스에서 '피벗'이라는 요소를 선택합니다.
2. 기준선 값보다 작은 모든 요소는 기준선 앞에 배치되고 기준선 값보다 큰 모든 요소는 기준선 뒤에 배치되도록 시퀀스를 재정렬합니다(양쪽에 동일한 숫자가 배치될 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.
3. 기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.

구현 코드는 다음과 같습니다.

function quickSort(arr, bt, ed) {
  if (bt < ed) {
    var pivot = findPartition(arr, bt, ed);
    quickSort(arr, bt, pivot - 1);
    quickSort(arr, pivot + 1, ed);
  }
}

function findPartition(arr, bt, ed) {
  var stand = arr[bt];

  while (bt < ed) {
    while (bt < ed && arr[ed] >= stand) {
      ed --;
    }
    if (bt < ed) {
      arr[bt ++] = arr[ed];
    }
    while (bt < ed && arr[bt] <= stand) {
      bt ++;
    }
    if (bt < ed) {
      arr[ed --] = arr[bt]; 
    }
  }

  arr[bt] = stand;
  return bt;
}

시간 복잡도는 O(nlogn)입니다.
병합 정렬

또한 매우 고전적인 정렬 알고리즘입니다. 고전적인 정렬 알고리즘을 복습하기 위해 js를 배우는 기회를 얻었습니다. 병합 정렬에 대한 아이디어는 내 블로그인 병합 정렬을 참조하세요. 여기서는 js 구현만 작성합니다.

function mergeSort(arr, bt, ed) {
  if (bt < ed) {
    var mid = bt + parseInt((ed - bt) / 2);
    mergeSort(arr, bt, mid);
    mergeSort(arr, mid + 1, ed);
    mergeArray(arr, bt, mid, ed);    
  }
}

function mergeArray(arr, bt, mid, ed) {
  var mArr = [];
  var i = bt, j = mid + 1;
  while (i <= mid && j <= ed) {
    if (arr[i] <= arr[j]) {
      mArr.push(arr[i++]);
    } else {
      mArr.push(arr[j ++]);
    }
  }

  if (i <= mid) {
    mArr = mArr.concat(arr.slice(i, mid + 1));
  }

  if (j <= ed) {
    mArr = mArr.concat(arr.slice(j, ed + 1));
  }

  for (var h = 0; h < mArr.length; h ++) {
    arr[bt + h] = mArr[h];
  }
}

병합 정렬을 작성할 때 또 다른 작은 에피소드가 있었습니다. js는 자동으로 반올림할 수 없어서 나중에 parsInt 메서드를 사용했는데 매우 귀엽습니다.