Как реализовать сортировку целых чисел в Clojure?

Скажем, у меня есть массив целых чисел xs, принимающих значения от 0 до max, и мне нужно отсортировать его за время O(n), поэтому я не могу просто выполнить (sort xs).

Есть ли способ сделать это с помощью функции frequencies?

На другом языке я бы затем сделал for для перебора целых чисел от 0 до max, и для каждого значения x в этом диапазоне искал (frequencies x), а затем делал repeat (frequencies x) x или что-то в этом роде.

Крайне важно, что мне нужно делать это в ПОРЯДКЕ от меньшего к большему, что делает все это своего рода. Поэтому я НЕ хочу просто map каждого числа в xs.

Есть идеи для идиоматического решения в стиле clojure?

Спасибо.


sorting clojure counting-sort
person R u c k s a c k    schedule 28.02.2018    source источник
comment
Не спешите отмахиваться от (sort xs). Вероятно, это быстрее, чем любой код, который вы могли бы написать. Если вам действительно нужно индивидуальное решение, посмотрите библиотеку data.int-map для Работа с целочисленными ключами.   -  person miner49r    schedule 04.03.2018
comment
Вы не можете сделать лучше, чем (sort xs). Когда вы сложите стоимость (frequencies xs) и добавите много (repeat frequencies x) x), получится больше, чем (sort xs).   -  person Alan Thompson    schedule 04.05.2018

Ответы (2)


arrow_upward
0
arrow_downward

Обновление вектора не совсем O (1), но вы можете использовать это для создания счетчиков для каждого элемента:

(defn counting-sort [s]
  (if (empty? s)
    s
    (let [counts (reduce (fn [v e]
                           (update v e inc))
                         (vec (repeat (inc (apply max s)) 0))
                         s)]
      (apply concat (map-indexed #(repeat %2 %1) counts)))))
person Lee    schedule 28.02.2018
comment
Спасибо - придется грок это. Как заставить это работать для bigints? - person R u c k s a c k; 01.03.2018
comment
@Rucksack - это уже работает, если элементы равны bigints, но если вам действительно нужен диапазон bigint, размер векторов частот будет слишком большим для подсчета сортировки. - person Lee; 01.03.2018

arrow_upward
0
arrow_downward

Ну, вы можете просто сделать то, что вы сказали с clojure:

(let [xs [1 2 1 4 1 5 1 8 7 7 7]
      fs (frequencies xs)
      max 10]
  (into [] 
    cat
    (for [i (range max) :when (contains? fs i)]
      (repeat (get fs i) i))))
person cfrick    schedule 01.03.2018
comment
О, круто, это то, что я изначально искал - не мог сам все это собрать, спасибо. Это все еще (почти) линейное время, как ответ @Lee? - person R u c k s a c k; 01.03.2018