0

Здраствуйте! В настоящий момент изучаю алгоритмы. Написал вот такой код быстрой сортировки на javascript:

        let sorted = [];
        function quickSort(arr) {

                if (arr.length < 2) {
                    return arr[0];
                } else {
                    let key = arr[0]
                    let less = [];
                    let more = [];

                    for (let i = 1; i < arr.length; i++) {
                        if (arr[i] <= key) {
                            less.push(arr[i])
                        } else {
                            more.push(arr[i])
                        }
                    }
                    if (less.length > 0) {
                        sorted.push(quickSort(less));
                    }
                    sorted.push(key);
                    if (more.length > 0) {
                        sorted.push(quickSort(more));
                    }

                }
        }

      quickSort([14, 8, 12, 45, 33, 3]);
      console.log(sorted);

let sorted = [];

function quickSort(arr) {

  if (arr.length < 2) {
    return arr[0];
  } else {
    let key = arr[0]
    let less = [];
    let more = [];

    for (let i = 1; i < arr.length; i++) {
      if (arr[i] <= key) {
        less.push(arr[i])
      } else {
        more.push(arr[i])
      }
    }
    if (less.length > 0) {
      sorted.push(quickSort(less));
    }
    sorted.push(key);
    if (more.length > 0) {
      sorted.push(quickSort(more));
    }

  }
}

quickSort([14, 8, 12, 45, 33, 3]);
console.log(sorted);

К сожалению, на выходе получается вот такой массив: [3, 8, 12, undefined, 14, 33, 45, undefined]

Собственно вопрос: в чём ошибка в коде и каким образом можно её исправить, чтобы в отсортированном списке не было undefined? Конечно, есть способ в лоб: создать новую переменную, присваивать ей возвращаемое значение функции sorted.push() и проверять её на undefined. Но предполагаю, что есть способ изящней. Заранее спасибо!

1 ответ 1

1

Потому что в ветке else Ваша функция ничего не возвращает.

function quickSort(arr, result) {
  if (arguments.length == 1) {
    result = [];
  }

  if (arr.length < 2) {
    result.push(arr[0]);
  } else {
    let key = arr[0]
    let less = [];
    let more = [];

    for (let i = 1; i < arr.length; i++) {
      if (arr[i] <= key) {
        less.push(arr[i])
      } else {
        more.push(arr[i])
      }
    }
    if (less.length > 0) {
      quickSort(less, result);
    }
    result.push(key);
    if (more.length > 0) {
      quickSort(more, result);
    }
  }

  return result;
}

var result = quickSort([14, 8, 12, 45, 33, 3]);
console.log(JSON.stringify(result));

result = quickSort([14, 8, 100, 12, 45, 33, 3]);
console.log(JSON.stringify(result));

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.