Сортировка вставками не работает в моем коде, написанном на Scala

Я пишу функцию для выполнения сортировки вставками. При написании кода я снова получаю тот же список, что и на выходе.

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, xs.tail)
}

def insert(x: Int, xs: List[Int]): List[Int] =
{
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)
}

Может кто-нибудь, пожалуйста, дайте мне знать, где я ошибаюсь.


scala insertion-sort
person Learner    schedule 26.07.2018    source источник
comment
Возможный дубликат реализации сортировки вставками в scala   -  person Manoj Kumar Dhakad    schedule 26.07.2018

Ответы (1)


arrow_upward
2
arrow_downward

Я думаю, вам не хватает небольшого рекурсивного вызова в вашей функции. Пожалуйста, обратитесь к приведенному ниже коду.

def insertionSort(xs: List[Int]): List[Int] =
{
  if (xs.isEmpty) Nil
  else insert(xs.head, insertionSort(xs.tail))
}


def insert(x: Int, xs: List[Int]): List[Int] =
{
  if (xs.isEmpty || x <= xs.head) x :: xs
  else xs.head :: insert(x, xs.tail)
}

Думаю, теперь это должно сработать.

person Chaitanya Waikar    schedule 26.07.2018
comment
Что-то вроде /* HERE ---> */ insertionSort(xs.tail) /* <--- HERE */ сработало бы ;) - person Andrey Tyukin; 26.07.2018
comment
В любом случае. Я удалил его полностью @AndreyTyukin - person Chaitanya Waikar; 26.07.2018