JavaScript의 삽입 정렬
이 기사에서는 JavaScript의 삽입 정렬 개념에 대해 설명하고 구현 예를 제공합니다.
JavaScript의 정렬 기술
최적성, 가속 및 더 적은 간격을 보장하기 위한 비전을 가진 관심 있는 개인이 다양한 분류 기술을 개발했습니다. 이 실행에서 삽입 정렬은 최악의 시간 복잡성이 O(n^2)인 반면 최상의 경우 O(n)임을 보여줍니다.
소량의 데이터를 정렬하려면 Array.prototype.sort()를 선택하는 것이 좋습니다. 바람직한 상황으로 O(n*logn)보다 나은 O(n)의 시간 복잡도를 제공합니다.
그러나 sort() 함수는 복잡한 개체 등이 있는 거대한 데이터 더미에 대해 잘 수행되지 않습니다. Array.prototype.sort() 함수에는 삽입 정렬이 구현되어 있으므로 JavaScript 기본 정렬 알고리즘이 사용됩니다. 효율적인 범주에 속하지 않습니다.
또한 코드 정렬 성능은 사용자가 사용하는 브라우저에 따라 달라집니다. Chrome V8은 Tim Sort(삽입 정렬 + 병합 정렬)를 사용하고 Firefox는 기본 병합 정렬을 사용합니다.
실제 시나리오에서 원시 데이터는 반드시 정렬되지 않은 것은 아닙니다. 대신 그들은 질서의 패턴을 따릅니다. 따라서 데이터를 처음부터 정렬할 필요가 없다고 말할 수 있습니다.
V8의 경우 어레이는 초기에 실행이라고 하는 블록으로 나뉩니다. 하위 수준의 이러한 실행은 삽입 정렬 원칙으로 정렬되고 나중에 병합 정렬 방식과 병합됩니다.
몇 개의 숫자나 개체로 작업하는 경우 팀 정렬은 O(n)의 시간 복잡도를 갖는 삽입 정렬로 작동합니다. 큰 데이터의 경우 V8 정렬은 O(n*logn)의 시간 복잡도를 갖는 병합 정렬로 작동합니다.
따라서 팀 정렬은 기존 병합 정렬보다 고도로 최적화되고 안정적인 정렬 기술입니다.
예제 섹션에서는 삽입 정렬의 기본 아이디어를 다루고 제약 조건이 있는 이유와 많은 것보다 나은 이유를 결정할 수 있습니다. 이전 부분에서 논의한 내용은 V8 엔진이 JavaScript 엔진이므로 삽입 정렬이 어떻게 사용되는지 설명합니다.
데모를 시작하겠습니다.
JavaScript에서 삽입 정렬 기술 구현
이러한 종류의 기본 개념은 한 손의 카드를 분류하는 것과 비교할 수 있습니다. 처음에는 카드를 첫 번째로 설정하고 나중에 정렬할 다음 카드(첫 번째 세트 카드라고 함)를 선택합니다.
여기에서 다음 카드의 이름은 key이며 key가 첫 번째 카드보다 크면 그대로 유지합니다. 그렇지 않으면 키와 첫 번째 카드의 위치를 바꿉니다. 그리고 이것은 전체 배열이 순회되고 정렬될 때까지 반복됩니다.
코드 라인을 확인해 봅시다.
코드 조각:
var arr = [4, 2, 3, 1, 7];
var size = arr.length;
for (var i = 1; i < size; i++) {
var key = arr[i];
var j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
console.log(arr)
출력:
보시다시피 삽입 정렬은 키를 저장하기 위해 1 슬롯이 아닌 다른 공간 배열을 차지하지 않기 때문에 O(1)의 공간 복잡도를 가집니다. 따라서 최적의 공간을 의식한다면 이 종류가 적합할 것입니다.
