Реализация алгоритма быстрой стабильной сортировки в javascript

Question

Я хочу отсортировать массив из 200-300 объектов, сортируя по определенному ключу и заданному порядку (asc / desc). Порядок результатов должен быть последовательным и стабильным.

Какой алгоритм лучше всего использовать, и не могли бы вы привести пример его реализации в javascript?

Спасибо!

Answer 1

Стабильную сортировку можно получить из нестабильной функции сортировки.

Перед сортировкой вы получаете положение всех элементов. В ваших условиях сортировки, если оба элемента равны, вы сортируете по позиции.

Тад! У вас стабильная сортировка.

Я написал статью об этом в своем блоге, если вы хотите узнать больше об этой технике и как ее реализовать: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Answer 2

Так как вы ищете что-то стабильное, сортировка слиянием должна подойти.

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

EDIT:

Согласно этому post , похоже, что Array.Sort в некоторых реализациях использует сортировку слиянием.

Answer 3

Я знаю, что на этот вопрос уже был дан ответ, но у меня в буфере обмена есть хорошая стабильная реализация сортировки слиянием для 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"];

Answer 4

Несколько более короткая версия того же самого, использующая функции 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 }
]

Ресурсы

• Википедии
• MDN
• JSFiddle

Обновление

Array.prototype.sort теперь стабильно работает в V8 v7.0 / Chrome 70!

Ранее V8 использовал нестабильную QuickSort для массивов с более чем 10 элементами. Теперь мы используем стабильный алгоритм TimSort.

источник

Answer 5

Вы можете использовать следующий 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) + '%')

При выполнении тестов производительности, реализованных выше, stableSort() работает примерно на 57% от скорости sort() в Chrome версии 59-61.

Использование .bind(compareFunction) в обернутой анонимной функции в stableSort() повысило эту относительную производительность примерно с 38%, избегая ненужной ссылки в области видимости на compareFunction при каждом вызове, назначив ее вместо контекста.

Обновление

Изменен троичный оператор на логическое короткое замыкание, которое, как правило, работает лучше в среднем (по-видимому, разница в эффективности составляет 2-3%).

Answer 6

Следующее сортирует предоставленный массив, применяя предоставленную функцию сравнения, возвращая исходное сравнение индекса, когда функция сравнения возвращает 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);
});

Answer 7

Вы также можете использовать Timsort. Это действительно сложный алгоритм (более 400 строк, поэтому здесь нет исходного кода), поэтому посмотрите описание Википедии или используйте одну из существующих реализаций JavaScript:

Реализация GPL 3 . Упакован как Array.prototype.timsort. Представляется точной перепиской кода Java.

Реализация общественного достояния Имеется в виду учебник, пример кода показывает только его использование с целыми числами.

Timsort - это высокооптимизированный гибрид сортировки слиянием и случайной сортировки, который является алгоритмом сортировки по умолчанию в Python и Java (1.7+). Это сложный алгоритм, поскольку он использует разные алгоритмы для многих особых случаев. Но в результате это очень быстро в самых разных обстоятельствах.

Answer 8

Вот стабильная реализация. Он работает с использованием собственной сортировки, но в случаях, когда элементы сравниваются как равные, вы разрываете связи, используя исходную позицию индекса.

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 , чтобы принять пользовательскую функцию компаратора, и это было намного быстрее.

Answer 9

Простое объединениеСортировать из 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));

Answer 10

Так что мне нужна была стабильная сортировка для моего приложения React + Redux, и ответ Vjeux здесь помог мне.Тем не менее, мое (общее) решение кажется отличным от других, которые я вижу здесь до сих пор, поэтому я делюсь им на случай, если у кого-то еще есть подходящий вариант использования:

• Я действительно просто хочу иметьчто-то похожее на sort() API, где я могу передать функцию сравнения.
• Иногда я могу сортировать на месте, а иногда мои данные неизменны (потому что Redux), и мне нужноотсортированная копия вместо.Поэтому мне нужна стабильная функция сортировки для каждого варианта использования.
• ES2015.

Мое решение - создать типизированный массив indices, а затем использовать функцию сравнения для сортировки.эти индексы основаны на сортируемом массиве.Затем мы можем использовать отсортированный 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;
}