Бесконечная рекурсия в JavaScript quicksort?

Вот код quicksort, который я написал. Функция не работает, потому что она не может попасть в базовый регистр. Если я зарегистрирую стержень, r и l на консоли, они остаются теми же, независимо от того, сколько раз вызывается функция сортировки. Поэтому я задаюсь вопросом, действительно ли аргумент l, r не передается в функцию как данные. Почему это произошло?

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}

Ответ 1

Я думаю, что проблема здесь в том, что ваш шаг разбиения не обязательно сокращает входной массив. Например, проследите, что произойдет, если вы попытаетесь сортировать [1, 2]. В этом случае ваш элемент pivot будет элементом 2. Так как 1 > 2 является ложным, в список l добавляется 1. Так как 2 > 2 ложно, в список l добавляется 2. В результате ваш рекурсивный вызов в списке l будет иметь те же аргументы, что и ваш первоначальный вызов, что вызывает бесконечную рекурсию.

Чтобы исправить это, попробуйте разбить вход на три списка - одно из меньших значений, одно из равных значений и одно из больших значений. Этот код показан здесь:

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

Эта новая версия явно группирует равные элементы в свой собственный список, поэтому они не рекурсивно сортируются по одному из рекурсивных вызовов. Он также изящно обрабатывает повторяющиеся элементы.

Надеюсь, это поможет!

Ответ 2

Если вы выберете наибольшее значение массива в качестве элемента pivot, тогда все значения data будут попадать в массив l и ни один из r. Таким образом, рекурсия никогда не прекратится (и сохраните l, r и pivot при одинаковых значениях). Если это не упражнение мозга, использование data.sort() должно сделать лучшую работу.;)

Ответ 3

JavaScript передает объекты по ссылке (массивы тоже являются объектами). Если вы хотите передать их по значению, вам нужно использовать функцию сращивания, как описано здесь.

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