Реализация алгоритма быстрой стабильной сортировки в 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;
}

РЕДАКТИРОВАТЬ:

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

Answer 3

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

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

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

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

другой ответ ссылался на это, но не опубликовал кодек.

но это не быстро в соответствии с моим тестом. Я изменил сортировку слиянием, чтобы принять пользовательскую функцию компаратора, и это было намного быстрее.

Answer 8

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

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

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

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

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

Вот как можно расширить объект Array по умолчанию в JS с помощью метода-прототипа, использующего MERGE SORT. Этот метод позволяет выполнять сортировку по определенному ключу (первый параметр) и заданному порядку ("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');

Answer 11

Согласно блогу разработчиков v8 и https://caniuse.com/ Array.sortуже стабильна, как того требует спецификация в современных браузерах, поэтому вам не нужно создавать собственное решение. Единственное исключение, которое я вижу, - это Edge, который скоро должен перейти на хром и поддерживать его.

Answer 12

function sort(data){
    var result=[];
    var array = data;
    const array2=data;
    const len=array2.length;
    for(var i=0;i<=len-1;i++){
    var min = Math.min.apply(Math,array)
    result.push(min);
    var index=array.indexOf(min)
    array.splice(index,1);
    }
    return result;
}   
sort([9,8,5,7,9,3,9,243,4,5,6,3,4,2,4,7,4,9,55,66,33,66]);

Answer 13

Я должен сортировать многомерные массивы по произвольному столбцу, а затем по другому. Я использую эту функцию для сортировки:

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" принимают решения, которые могут быть неправильными.

Это тоже чертовски быстро.

Answer 14

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

Answer 15

Поэтому мне понадобилась стабильная сортировка для моего приложения 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;
}

Answer 16

Счетная сортировка выполняется быстрее, чем сортировка слиянием (она выполняется за 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