Наивная быстрая сортировка в Clojure

Question

Я изучаю clojure и хотел написать свою наивную быструю сортировку. Эта реализация разрезает массив (вектор) пополам и обрабатывает их рекурсивно. Проблема заключается в том, что этот код генерирует исключение NullPointerException, когда массив (вектор) имеет размер 1 только в конце рекурсии. Почему это так?

(ns qsort)

(defn qsort [arr] 
(println "arr" arr)
(def cnt (count arr))
(def pivotidx (if (> cnt 1)
  (int (/ cnt 2))
  -1
))

(print "pivotidx:" pivotidx " ")
(if (> pivotidx -1)
  ((def pivotval (nth arr pivotidx))
  (println "pivotval:" pivotval " ")
  (def right (filter #(> % pivotval ) arr))
  (def left (filter #(< % pivotval) arr))
  (println "left" left "right" right)
  (concat (qsort left) [pivot] (qsort right))
  )
  arr
)
) 


(defn sortme [] (qsort [3 5 8 9 1 7 12 13 2 14 0]))

Answer 1

Другие ответы уже проделали хорошую работу по описанию «правильного» способа ведения дел, который по совпадению также решает вашу проблему. Тем не менее, ваш NPE вызван

((def pivotval (nth arr pivotidx))
 ...more stuff...)

Вы не можете просто использовать () для группировки элементов: (foo) в lisp означает вызов функции foo; аналогично ((bar) (foo)) означает:

1. Позвоните bar, сохранив результат как x
2. Звоните foo. сохранение результата как y
3. вызов функции x с аргументом y

Поскольку def не возвращает функцию, вызов ее результата с шестью или семью аргументами вызовет проблему.

Вместо этого, если вы хотите сгруппировать вещи, вы должны использовать специальную форму do. (do (foo) (bar)) означает «вызов foo, а затем возврат результата вызова bar».

Answer 2

Правильное использование let вместо def правильно делает:

(defn qsort [arr]
(println "arr" arr)
(let 
 [
  cnt (count arr)
  pivotidx (if (> cnt 1) (int (/ cnt 2)) -1)
 ]
(print "pivotidx:" pivotidx " ")

(if (> pivotidx -1) 
 (let
   [
    pivotval (nth arr pivotidx)
    right (filter #(> % pivotval ) arr)
    left (filter #(< % pivotval) arr)
   ] 
 (println "pivotval:" pivotval " ")
 (println "left" left "right" right)
 (concat (qsort left) [pivotval] (qsort right))
 )
 arr) ))

И затем

(qsort [3 5 8 9 1 7 12 13 2 14 0])

возвращает:

(0 1 2 3 5 7 8 9 12 13 14)

Answer 3

(defn qsort
  [l]
  (cond
    (empty? l) '()
    :else (let [f (first l)
                smaller (filter #(<= % f) (rest l))
                bigger (filter #(> % f) (rest l))]
            (concat (qsort smaller) [f] (qsort bigger)))))

Answer 4

Похоже, если массив имеет длину 1, то:

• pivotidx будет 0
• pivotval будет первым (единственным) элементом
• вправо и влево будут пустыми (ноль)
• следовательно, вы получите исключение нулевого указателя при следующей рекурсии (возможно, когда вы попытаетесь посчитать длину nil ....)

Некоторые советы / другие ошибки, которые нужно исправить

• Поместить тест для нулевых или пустых списков в начале функции
• Не используйте def внутри функции - используйте вместо нее (пусть [name value] ...) *
• Я думаю, что ваша логика разбиения пропустит дубликаты стержня - проверяя этот случай!
• Не уверен, почему вы берете значение pivot в середину массива, обычно проще всего использовать (first arr) в качестве pivot. Единственный случай, когда вы хотите выбрать среднее значение, это когда вы знаете, что данные уже почти отсортированы ....