자바 스크립트에서 빠르고 안정적인 정렬 알고리즘 구현
특정 키와 지정된 순서 (asc / desc)를 기준으로 약 200-300 개의 개체 배열을 정렬하려고합니다. 결과 순서는 일관성 있고 안정적이어야합니다.
사용하기에 가장 좋은 알고리즘은 무엇이며 자바 스크립트로 구현 된 예를 제공 할 수 있습니까?
감사!
비 안정 정렬 기능에서 안정적인 정렬을 얻을 수 있습니다.
정렬하기 전에 모든 요소의 위치를 얻습니다. 정렬 조건에서 두 요소가 같으면 위치를 기준으로 정렬합니다.
타다! 당신은 안정적인 종류를 가지고 있습니다.
이 기술과 구현 방법에 대해 더 알고 싶다면 내 블로그에 기사를 작성했습니다. http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html
안정적인 것을 찾고 있기 때문에 병합 정렬이 수행되어야합니다.
http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/
코드는 위 웹 사이트에서 찾을 수 있습니다.
function mergeSort(arr)
{
if (arr.length < 2)
return arr;
var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
편집하다:
이 게시물 에 따르면 일부 구현에서는 Array.Sort가 병합 정렬을 사용하는 것처럼 보입니다.
이 질문에 대한 답변은 얼마 동안 이루어졌지만 클립 보드에 Array 및 jQuery에 대한 안정된 병합 정렬 구현이 있으므로 향후 일부 검색자가 유용하게 사용할 수 있기를 바라며 공유하겠습니다.
일반 Array.sort구현 과 마찬가지로 고유 한 비교 기능을 지정할 수 있습니다 .
이행
// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn't pollute the global
// namespace, but we don't put it in $(document).ready, since it's
// not dependent on the DOM
(function() {
// expose to Array and jQuery
Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;
function mergeSort(compare) {
var length = this.length,
middle = Math.floor(length / 2);
if (!compare) {
compare = function(left, right) {
if (left < right)
return -1;
if (left == right)
return 0;
else
return 1;
};
}
if (length < 2)
return this;
return merge(
this.slice(0, middle).mergeSort(compare),
this.slice(middle, length).mergeSort(compare),
compare
);
}
function merge(left, right, compare) {
var result = [];
while (left.length > 0 || right.length > 0) {
if (left.length > 0 && right.length > 0) {
if (compare(left[0], right[0]) <= 0) {
result.push(left[0]);
left = left.slice(1);
}
else {
result.push(right[0]);
right = right.slice(1);
}
}
else if (left.length > 0) {
result.push(left[0]);
left = left.slice(1);
}
else if (right.length > 0) {
result.push(right[0]);
right = right.slice(1);
}
}
return result;
}
})();
사용 예
var sorted = [
'Finger',
'Sandwich',
'sandwich',
'5 pork rinds',
'a guy named Steve',
'some noodles',
'mops and brooms',
'Potato Chip Brand® chips'
].mergeSort(function(left, right) {
lval = left.toLowerCase();
rval = right.toLowerCase();
console.log(lval, rval);
if (lval < rval)
return -1;
else if (lval == rval)
return 0;
else
return 1;
});
sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];
화살표 함수 및 구조 분해와 같은 ES2017 기능을 사용하는 동일한 것의 약간 더 짧은 버전 :
함수
var stableSort = (arr, compare) => arr
.map((item, index) => ({item, index}))
.sort((a, b) => compare(a.item, b.item) || a.index - b.index)
.map(({item}) => item)
입력 배열을 받아들이고 함수를 비교합니다.
stableSort([5,6,3,2,1], (a, b) => a - b)
또한 내장 Array.sort () 함수 와 같이 내부 정렬을 만드는 대신 새 배열을 반환 합니다.
테스트
다음 input배열을 사용하면 처음에는 다음과 같이 정렬됩니다 weight.
// sorted by weight
var input = [
{ height: 100, weight: 80 },
{ height: 90, weight: 90 },
{ height: 70, weight: 95 },
{ height: 100, weight: 100 },
{ height: 80, weight: 110 },
{ height: 110, weight: 115 },
{ height: 100, weight: 120 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 100, weight: 135 },
{ height: 75, weight: 140 },
{ height: 70, weight: 140 }
]
그런 다음 다음을 height사용하여 정렬하십시오 stableSort.
stableSort(input, (a, b) => a.height - b.height)
결과 :
// Items with the same height are still sorted by weight
// which means they preserved their relative order.
var stable = [
{ height: 70, weight: 95 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 70, weight: 140 },
{ height: 75, weight: 140 },
{ height: 80, weight: 110 },
{ height: 90, weight: 90 },
{ height: 100, weight: 80 },
{ height: 100, weight: 100 },
{ height: 100, weight: 120 },
{ height: 100, weight: 135 },
{ height: 110, weight: 115 }
]
그러나 input내장 Array.sort()(Chrome / NodeJS에서)을 사용하여 동일한 배열 정렬 :
input.sort((a, b) => a.height - b.height)
보고:
var unstable = [
{ height: 70, weight: 140 },
{ height: 70, weight: 95 },
{ height: 70, weight: 125 },
{ height: 70, weight: 130 },
{ height: 75, weight: 140 },
{ height: 80, weight: 110 },
{ height: 90, weight: 90 },
{ height: 100, weight: 100 },
{ height: 100, weight: 80 },
{ height: 100, weight: 135 },
{ height: 100, weight: 120 },
{ height: 110, weight: 115 }
]
자원
최신 정보
Array.prototype.sort이제 V8 v7.0 / Chrome 70에서 안정적입니다!이전에 V8은 요소가 10 개 이상인 배열에 대해 불안정한 QuickSort를 사용했습니다. 이제 안정적인 TimSort 알고리즘을 사용합니다.
이 답변에서 만든 어설 션을 기반으로 기본 구현에 관계없이 다음 polyfill을 사용하여 안정적인 정렬을 구현할 수 있습니다 .
// ECMAScript 5 polyfill
Object.defineProperty(Array.prototype, 'stableSort', {
configurable: true,
writable: true,
value: function stableSort (compareFunction) {
'use strict'
var length = this.length
var entries = Array(length)
var index
// wrap values with initial indices
for (index = 0; index < length; index++) {
entries[index] = [index, this[index]]
}
// sort with fallback based on initial indices
entries.sort(function (a, b) {
var comparison = Number(this(a[1], b[1]))
return comparison || a[0] - b[0]
}.bind(compareFunction))
// re-map original array to stable sorted values
for (index = 0; index < length; index++) {
this[index] = entries[index][1]
}
return this
}
})
// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)))
const alwaysEqual = () => 0
const isUnmoved = (value, index) => value === array[index]
// not guaranteed to be stable
console.log('sort() stable?', array
.slice()
.sort(alwaysEqual)
.every(isUnmoved)
)
// guaranteed to be stable
console.log('stableSort() stable?', array
.slice()
.stableSort(alwaysEqual)
.every(isUnmoved)
)
// performance using realistic scenario with unsorted big data
function time(arrayCopy, algorithm, compare) {
var start
var stop
start = performance.now()
algorithm.call(arrayCopy, compare)
stop = performance.now()
return stop - start
}
const ascending = (a, b) => a - b
const msSort = time(array.slice(), Array.prototype.sort, ascending)
const msStableSort = time(array.slice(), Array.prototype.stableSort, ascending)
console.log('sort()', msSort.toFixed(3), 'ms')
console.log('stableSort()', msStableSort.toFixed(3), 'ms')
console.log('sort() / stableSort()', (100 * msSort / msStableSort).toFixed(3) + '%')위에서 구현 된 성능 테스트를 실행하면 Chrome 버전 59-61 stableSort()에서 속도의 약 57 %로 실행되는 것으로 보입니다 sort().
사용 .bind(compareFunction)내에 싸여 익명 함수 stableSort()에 불필요한 범위의 기준 피함으로써 약 38 %의 상대 성능이 승압 compareFunction대신 문맥에 할당하여 각 호에있다.
최신 정보
삼항 연산자를 논리적 단락으로 변경하여 평균적으로 더 나은 성능을 발휘하는 경향이 있습니다 (효율성에서 2-3 % 차이를 만드는 것으로 나타남).
다음은 제공된 비교 함수를 적용하여 제공된 배열을 정렬하고 비교 함수가 0을 반환 할 때 원래 인덱스 비교를 반환합니다.
function stableSort(arr, compare) {
var original = arr.slice(0);
arr.sort(function(a, b){
var result = compare(a, b);
return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
});
return arr;
}
아래 예제는 동일한 성의 순서를 유지하면서 성별로 이름 배열을 정렬합니다.
var names = [
{ surname: "Williams", firstname: "Mary" },
{ surname: "Doe", firstname: "Mary" },
{ surname: "Johnson", firstname: "Alan" },
{ surname: "Doe", firstname: "John" },
{ surname: "White", firstname: "John" },
{ surname: "Doe", firstname: "Sam" }
]
function stableSort(arr, compare) {
var original = arr.slice(0);
arr.sort(function(a, b){
var result = compare(a, b);
return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
});
return arr;
}
stableSort(names, function(a, b) {
return a.surname > b.surname ? 1 : a.surname < b.surname ? -1 : 0;
})
names.forEach(function(name) {
console.log(name.surname + ', ' + name.firstname);
});다음은 안정적인 구현입니다. 기본 정렬을 사용하여 작동하지만 요소가 동일한 것으로 비교되는 경우 원래 인덱스 위치를 사용하여 연결을 끊습니다.
function stableSort(arr, cmpFunc) {
//wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position
var arrOfWrapper = arr.map(function(elem, idx){
return {elem: elem, idx: idx};
});
//sort the wrappers, breaking sorting ties by using their elements orig index position
arrOfWrapper.sort(function(wrapperA, wrapperB){
var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem);
return cmpDiff === 0
? wrapperA.idx - wrapperB.idx
: cmpDiff;
});
//unwrap and return the elements
return arrOfWrapper.map(function(wrapper){
return wrapper.elem;
});
}
철저하지 않은 시험
var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){
return a.a - b.a;
});
console.log(res);
이것에 대한 또 다른 대답이 암시되었지만 코드를 게시하지 않았습니다.
그러나 내 벤치 마크 에 따르면 빠르지 않습니다 . 사용자 정의 비교기 기능을 허용 하도록 병합 정렬 impl 을 수정했으며 훨씬 더 빠릅니다.
Timsort를 사용할 수도 있습니다. 이것은 정말 복잡한 알고리즘 (400 줄 이상이므로 여기에 소스 코드가 없음)이므로 Wikipedia의 설명을 참조 하거나 기존 JavaScript 구현 중 하나를 사용 하십시오 .
GPL 3 구현 . Array.prototype.timsort로 패키징됩니다. Java 코드를 정확히 재 작성한 것으로 보입니다.
퍼블릭 도메인 구현 은 튜토리얼을 의미하며, 샘플 코드는 정수와 함께 사용하는 방법 만 보여줍니다.
Timsort는 mergesort 및 shuffle 정렬의 고도로 최적화 된 하이브리드이며 Python 및 Java (1.7+)의 기본 정렬 알고리즘입니다. 많은 특수한 경우에 다른 알고리즘을 사용하기 때문에 복잡한 알고리즘입니다. 그러나 결과적으로 다양한 상황에서 매우 빠릅니다.
http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/ 의 간단한 mergeSort
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
function mergeSort(arr)
{
if (arr.length < 2)
return arr;
var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
console.log(mergeSort(a));
임의의 열로 다차원 배열을 정렬 한 다음 다른 열로 정렬해야합니다. 이 기능을 사용하여 정렬합니다.
function sortMDArrayByColumn(ary, sortColumn){
//Adds a sequential number to each row of the array
//This is the part that adds stability to the sort
for(var x=0; x<ary.length; x++){ary[x].index = x;}
ary.sort(function(a,b){
if(a[sortColumn]>b[sortColumn]){return 1;}
if(a[sortColumn]<b[sortColumn]){return -1;}
if(a.index>b.index){
return 1;
}
return -1;
});
}
ary.sort는 "sort"함수의 일부 구현이 옳지 않을 수있는 결정을 내리는 0을 반환하지 않습니다.
이것도 꽤 빠르다.
다음은 MERGE SORT를 활용하는 프로토 타입 메소드로 JS 기본 Array 객체를 확장하는 방법 입니다. 이 방법을 사용하면 특정 키 (첫 번째 매개 변수) 및 지정된 순서 (두 번째 매개 변수로 'asc'/ 'desc')를 정렬 할 수 있습니다.
Array.prototype.mergeSort = function(sortKey, direction){
var unsortedArray = this;
if(unsortedArray.length < 2) return unsortedArray;
var middle = Math.floor(unsortedArray.length/2);
var leftSubArray = unsortedArray.slice(0,middle).mergeSort(sortKey, direction);
var rightSubArray = unsortedArray.slice(middle).mergeSort(sortKey, direction);
var sortedArray = merge(leftSubArray, rightSubArray);
return sortedArray;
function merge(left, right) {
var combined = [];
while(left.length>0 && right.length>0){
var leftValue = (sortKey ? left[0][sortKey] : left[0]);
var rightValue = (sortKey ? right[0][sortKey] : right[0]);
combined.push((direction === 'desc' ? leftValue > rightValue : leftValue < rightValue) ? left.shift() : right.shift())
}
return combined.concat(left.length ? left : right)
}
}위의 스 니펫을 브라우저 콘솔에 드롭 한 후 다음을 시도하여 직접 테스트 할 수 있습니다.
var x = [2,76,23,545,67,-9,12];
x.mergeSort(); //[-9, 2, 12, 23, 67, 76, 545]
x.mergeSort(undefined, 'desc'); //[545, 76, 67, 23, 12, 2, -9]
또는 객체 배열의 특정 필드를 기준으로 정렬합니다.
var y = [
{startTime: 100, value: 'cat'},
{startTime: 5, value: 'dog'},
{startTime: 23, value: 'fish'},
{startTime: 288, value: 'pikachu'}
]
y.mergeSort('startTime');
y.mergeSort('startTime', 'desc');
그래서 React + Redux 앱에 안정적인 정렬이 필요했고 Vjeux의 답변이 도움이되었습니다. 그러나 내 (일반) 솔루션은 지금까지 여기에서 본 다른 솔루션과 다르게 보이므로 다른 사람이 일치하는 사용 사례가있는 경우를 대비하여 공유하고 있습니다.
- 나는
sort()비교기 함수를 전달할 수 있는 API 와 비슷한 것을 정말로 원합니다 . - 때로는 제자리에서 정렬 할 수 있고 때로는 데이터가 변경 불가능하고 (Redux 때문에) 대신 정렬 된 복사본이 필요합니다. 따라서 각 사용 사례에 대해 안정적인 정렬 기능이 필요합니다.
- ES2015.
내 솔루션은 형식화 된 배열을 indices만든 다음 비교 함수를 사용하여 정렬 할 배열을 기반으로 이러한 인덱스 를 정렬하는 것 입니다. 그런 다음 sorted indices를 사용하여 원본 배열을 정렬하거나 단일 패스로 정렬 된 복사본을 만들 수 있습니다. 혼란 스러우면 다음과 같이 비교 함수를 일반적으로 전달하는 방식으로 생각하십시오.
(a, b) => {
/* some way to compare a and b, returning -1, 0, or 1 */
};
이제 대신 다음을 사용합니다.
(i, j) => {
let a = arrayToBeSorted[i], b = arrayToBeSorted[j];
/* some way to compare a and b, returning -1 or 1 */
return i - j; // fallback when a == b
}
속도가 좋습니다. 기본적으로 내장 정렬 알고리즘은 끝에 두 개의 선형 패스를 더하고 포인터 간접 오버 헤드의 추가 레이어 하나입니다.
이 접근 방식에 대한 피드백을 받게되어 기쁩니다. 내 전체 구현은 다음과 같습니다.
/**
* - `array`: array to be sorted
* - `comparator`: closure that expects indices `i` and `j`, and then
* compares `array[i]` to `array[j]` in some way. To force stability,
* end with `i - j` as the last "comparison".
*
* Example:
* ```
* let array = [{n: 1, s: "b"}, {n: 1, s: "a"}, {n:0, s: "a"}];
* const comparator = (i, j) => {
* const ni = array[i].n, nj = array[j].n;
* return ni < nj ? -1 :
* ni > nj ? 1 :
* i - j;
* };
* stableSortInPlace(array, comparator);
* // ==> [{n:0, s: "a"}, {n:1, s: "b"}, {n:1, s: "a"}]
* ```
*/
function stableSortInPlace(array, comparator) {
return sortFromIndices(array, findIndices(array, comparator));
}
function stableSortedCopy(array, comparator){
let indices = findIndices(array, comparator);
let sortedArray = [];
for (let i = 0; i < array.length; i++){
sortedArray.push(array[indices[i]]);
}
return sortedArray;
}
function findIndices(array, comparator){
// Assumes we don't have to worry about sorting more than
// 4 billion elements; if you know the upper bounds of your
// input you could replace it with a smaller typed array
let indices = new Uint32Array(array.length);
for (let i = 0; i < indices.length; i++) {
indices[i] = i;
}
// after sorting, `indices[i]` gives the index from where
// `array[i]` should take the value from, so to sort
// move the value at at `array[indices[i]]` to `array[i]`
return indices.sort(comparator);
}
// If I'm not mistaken this is O(2n) - each value is moved
// only once (not counting the vacancy temporaries), and
// we also walk through the whole array once more to check
// for each cycle.
function sortFromIndices(array, indices) {
// there might be multiple cycles, so we must
// walk through the whole array to check.
for (let k = 0; k < array.length; k++) {
// advance until we find a value in
// the "wrong" position
if (k !== indices[k]) {
// create vacancy to use "half-swaps" trick,
// props to Andrei Alexandrescu
let v0 = array[k];
let i = k;
let j = indices[k];
while (j !== k) {
// half-swap next value
array[i] = array[j];
// array[i] now contains the value it should have,
// so we update indices[i] to reflect this
indices[i] = i;
// go to next index
i = j;
j = indices[j];
}
// put original array[k] back in
// and update indices
array[i] = v0;
indices[i] = i;
}
}
return array;
}
나는 이것이 많은 답변을 받았다는 것을 알고 있습니다. 나는 그것을 찾고 여기에 도착한 사람을 위해 빠른 TS 구현을 게시하고 싶었습니다.
export function stableSort<T>( array: T[], compareFn: ( a: T, b: T ) => number ): T[] {
const indices = array.map( ( x: T, i: number ) => ( { element: x, index: i } ) );
return indices.sort( ( a, b ) => {
const order = compareFn( a.element, b.element );
return order === 0 ? a.index - b.index : order;
} ).map( x => x.element );
}
이 메서드는 기본 정렬처럼 더 이상 제자리에서 실행되지 않습니다. 또한 가장 효율적이지 않다는 점을 지적하고 싶습니다. O (n) 순서의 두 루프를 추가합니다. 정렬 자체는 O (n log (n)) 일 가능성이 높으므로 그보다 적습니다.
언급 된 솔루션 중 일부는 더 성능이 뛰어나며 내부 Array.prototype.sort.
(Javascript 솔루션의 경우 모든 유형을 제거하십시오)
계수 정렬은 병합 정렬 (O (n) 시간에 수행)보다 빠르며 정수에 사용하기위한 것입니다.
Math.counting_sort = function (m) {
var i
var j
var k
var step
var start
var Output
var hash
k = m.length
Output = new Array ()
hash = new Array ()
// start at lowest possible value of m
start = 0
step = 1
// hash all values
i = 0
while ( i < k ) {
var _m = m[i]
hash [_m] = _m
i = i + 1
}
i = 0
j = start
// find all elements within x
while ( i < k ) {
while ( j != hash[j] ) {
j = j + step
}
Output [i] = j
i = i + 1
j = j + step
}
return Output
}
예:
var uArray = new Array ()<br/>
var sArray = new Array ()<br/><br/>
uArray = [ 10,1,9,2,8,3,7,4,6,5 ]<br/>
sArray = Math.counting_sort ( uArray ) // returns a sorted array
'developer tip' 카테고리의 다른 글
| iOS 7에서 UINavigationbar 아래의 UISegmentedControl (0) | 2020.08.25 |
|---|---|
| 여러 열 집합 수집 (0) | 2020.08.25 |
| Visual Studio 2010은 잘못된 MDI 창에서 문서를 짜증나게 엽니 다. (0) | 2020.08.25 |
| Angular 2를 사용한 HTML5 이벤트 처리 (onfocus 및 onfocusout) (0) | 2020.08.25 |
| Rails에서 has_many 관계를 자동으로 정렬하려면 어떻게해야합니까? (0) | 2020.08.25 |