Chcę posortować tablicę około 200-300 obiektów, sortując według określonego klucza i podanej kolejności (rosnąco / malejąco). Kolejność wyników musi być spójna i stabilna.

Jaki byłby najlepszy algorytm do użycia i czy możesz podać przykład jego implementacji w javascript?

Dzięki!

Stabilne sortowanie można uzyskać dzięki niestabilnej funkcji sortowania.

Przed sortowaniem otrzymujesz pozycję wszystkich elementów. W twoim warunku sortowania, jeśli oba elementy są równe, sortujesz według pozycji.

Tada! Masz stabilny gatunek.

Napisałem o tym artykuł na swoim blogu, jeśli chcesz dowiedzieć się więcej o tej technice i jak ją wdrożyć: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Ponieważ szukasz czegoś stabilnego, sortowanie przez scalanie powinno wystarczyć.

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

Kod można znaleźć na powyższej stronie internetowej:

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;
}

EDYTOWAĆ:

Zgodnie z tym postem wygląda to tak, jak Array.Sort w niektórych implementacjach używa sortowania przez scalanie.

Nieco krótsza wersja tego samego, wykorzystująca funkcje ES2017, takie jak funkcje strzałek i destrukturyzacja:

Funkcjonować

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)

Akceptuje tablicę wejściową i funkcję porównania:

stableSort([5,6,3,2,1], (a, b) => a - b)

Zwraca również nową tablicę zamiast sortowania w miejscu, jak wbudowana funkcja Array.sort () .

Test

Jeśli weźmiemy następującą inputtablicę, początkowo posortowaną według 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 }
]

Następnie posortuj go, heightużywając stableSort:

stableSort(input, (a, b) => a.height - b.height)

Prowadzi do:

// 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 }
]

Jednak sortowanie tej samej inputtablicy za pomocą wbudowanej Array.sort()(w Chrome / NodeJS):

input.sort((a, b) => a.height - b.height)

Zwroty:

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 }
]

Zasoby

• Wikipedia
• MDN
• JSFiddle

Aktualizacja

Array.prototype.sort jest teraz stabilny w V8 v7.0 / Chrome 70!

Wcześniej V8 używał niestabilnego QuickSort dla tablic z więcej niż 10 elementami. Teraz używamy stabilnego algorytmu TimSort.

źródło

Wiem, że odpowiedź na to pytanie jest już od jakiegoś czasu, ale tak się składa, że ​​mam w schowku dobrą, stabilną implementację sortowania przez scalanie dla Array i jQuery, więc podzielę się nim w nadziei, że niektórzy przyszli użytkownicy uznają to za przydatne.

Umożliwia określenie własnej funkcji porównawczej, tak jak w przypadku zwykłej Array.sortimplementacji.

Realizacja

// 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;
  }
})();

Przykładowe użycie

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"];

Możesz użyć następującego wypełnienia, aby zaimplementować stabilne sortowanie niezależnie od natywnej implementacji, na podstawie stwierdzenia zawartego w tej odpowiedzi :

// 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) + '%')

stableSort()Wydaje się, że uruchomienie testów wydajności zaimplementowanych powyżej przebiega z prędkością około 57% szybkości sort()przeglądarki Chrome w wersji 59-61.

Użycie .bind(compareFunction)na opakowanej funkcji anonimowej w ramach stableSort()zwiększyło tę względną wydajność z około 38%, unikając niepotrzebnych odwołań o określonym zakresie do compareFunctionprzy każdym wywołaniu, przypisując je zamiast tego do kontekstu.

Aktualizacja

Zmieniono operator trójskładnikowy na logiczne zwarcie, które zwykle działa lepiej (wydaje się, że powoduje 2-3% różnicę w wydajności).

Poniższe polecenie sortuje podaną tablicę, stosując dostarczoną funkcję porównania, zwracając oryginalne porównanie indeksu, gdy funkcja porównująca zwraca 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;
}

Poniższy przykład sortuje tablicę imion według nazwiska, zachowując kolejność jednakowych nazwisk:

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);
});

Oto stabilna implementacja. Działa przy użyciu natywnego sortowania, ale w przypadkach, gdy elementy są porównywane jako równe, zrywasz więzi, używając oryginalnej pozycji indeksu.

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;
    });
}

nieprecyzyjny test

var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){
    return a.a - b.a;
});
console.log(res);

inna odpowiedź nawiązywała do tego, ale nie opublikowała kodu.

ale nie jest szybki według mojego punktu odniesienia . Zmodyfikowałem metodę sortowania przez scalanie, aby zaakceptować niestandardową funkcję komparatora, i było to znacznie szybsze.

Możesz także użyć Timsort. To naprawdę skomplikowany algorytm (ponad 400 wierszy, stąd brak kodu źródłowego), więc zobacz opis Wikipedii lub użyj jednej z istniejących implementacji JavaScript:

Wdrożenie GPL 3 . Pakowane jako Array.prototype.timsort. Wydaje się być dokładnym przepisaniem kodu Java.

Implementacja w domenie publicznej Przykładowy kod, który jest samouczkiem, pokazuje jego użycie tylko z liczbami całkowitymi.

Timsort jest wysoce zoptymalizowaną hybrydą scalania i sortowania losowego i jest domyślnym algorytmem sortowania w Pythonie i Javie (1.7+). Jest to skomplikowany algorytm, ponieważ używa różnych algorytmów w wielu szczególnych przypadkach. Ale w rezultacie jest niezwykle szybki w różnych okolicznościach.

Proste jedno scalenieSort z http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

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));

Muszę sortować tablice wielowymiarowe według dowolnej kolumny, a następnie według innej. Używam tej funkcji do sortowania:

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;
    });
}

Zauważ, że ary.sort nigdy nie zwraca zera, co oznacza, że ​​niektóre implementacje funkcji "sort" podejmują decyzje, które mogą być niewłaściwe.

To też jest cholernie szybkie.

Oto jak można rozszerzyć domyślny obiekt Array JS za pomocą prototypowej metody wykorzystującej MERGE SORT . Ta metoda pozwala na sortowanie według określonego klucza (pierwszy parametr) i podanej kolejności („rosnąco” / „desc” jako drugi parametr)

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)
  }
}

Możesz to sprawdzić samodzielnie, upuszczając powyższy fragment kodu w konsoli przeglądarki, a następnie próbując:

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]

Lub uporządkuj na podstawie określonego pola w tablicy obiektów:

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');

Potrzebowałem więc stabilnego sortowania dla mojej aplikacji React + Redux, a odpowiedź Vjeux pomogła mi. Jednak moje (ogólne) rozwiązanie wydaje się inne niż inne, które widzę tutaj do tej pory, więc udostępniam je na wypadek, gdyby ktoś inny miał pasujący przypadek użycia:

• Naprawdę chcę mieć coś podobnego do sort()API, w którym mogę przekazać funkcję komparatora.
• Czasami można sortować w miejscu, a czasami moje dane są niezmienne (bo Redux) i muszę posortowaną kopię zamiast. Dlatego potrzebuję stabilnej funkcji sortowania dla każdego przypadku użycia.
• ES2015.

Moim rozwiązaniem jest utworzenie tablicy o typie strukturalnym indices, a następnie użycie funkcji porównania do sortowania tych indeksów na podstawie tablicy, która ma być posortowana. Następnie możemy użyć posortowanego, indicesaby posortować oryginalną tablicę lub utworzyć posortowaną kopię w jednym przebiegu. Jeśli to jest mylące, pomyśl o tym w ten sposób: gdzie normalnie przekazujesz funkcję porównującą, taką jak:

(a, b) => { 
  /* some way to compare a and b, returning -1, 0, or 1 */ 
};

Zamiast tego używasz teraz:

(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
}

Szybkość jest dobra; jest to w zasadzie wbudowany algorytm sortowania, plus dwa liniowe przebiegi na końcu i jedna dodatkowa warstwa wskaźnika pośredniego narzutu.

Z przyjemnością otrzymuję informacje zwrotne na temat tego podejścia. Oto moja pełna implementacja:

/**
 * - `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;
}

Wiem, że udzielono wielu odpowiedzi. Chciałem tylko opublikować krótki wpis dotyczący implementacji TS dla każdego, kto wylądował tutaj, szukając tego.

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 );
}

Metoda nie działa już w miejscu, jak robi to sortowanie natywne. Chcę też zaznaczyć, że nie jest to najbardziej wydajne. Dodaje dwie pętle rzędu O (n). chociaż samo sortowanie jest najprawdopodobniej O (n log (n)), więc jest mniejsze niż to.

Niektóre z wymienionych rozwiązań są bardziej wydajne, myśląc, że może to być mniej kodu, również przy użyciu wewnętrznego Array.prototype.sort.

(Aby uzyskać rozwiązanie JavaScript, po prostu usuń wszystkie typy)

Zgodnie z blogiem deweloperów wersji 8, a caniuse.comArray.sort jest już stabilny zgodnie ze specyfikacją nowoczesnych przeglądarek, więc nie musisz tworzyć własnego rozwiązania. Jedynym wyjątkiem, jaki widzę, jest Edge, który wkrótce powinien przejść na chrom i również go wspierać.

Sortowanie z liczeniem jest szybsze niż sortowanie przez scalanie (działa w czasie O (n)) i jest przeznaczone do stosowania na liczbach całkowitych.

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
}

Przykład:

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