コピペ: Copy: selection_sort.clj

形式

Lisp

投稿日時

2020-09-16 05:39

公開期間

無期限

 (defrecord find-result [x ^long n])
 
 (defn find-next [lst mx x ^long n]
   (if (empty? lst)
     (find-result. x n)
     (let [h (first lst) t (rest lst)]
       (if (nil? x)
         (if (< h mx)
           (recur t mx h 1)
           (recur t mx nil 0))
         (if (or (< h x) (>= h mx))
           (recur t mx x n)
           (recur t mx h (if (= x h) (+ n 1) 1)))))))
 
 (defn find-largest2 [lst x n]
   (if (empty? lst)
     (find-result. x n)
     (let [h (first lst) t (rest lst)]
       (if (< h x)
         (recur t x n)
         (recur t h (if (= x h) (+ n 1) 1))))))
 
 (defn find-largest [lst]
   (find-largest2 (rest lst) (first lst) 1))
 
 (defn dup-list [dst x ^long n]
   (if (= 0 n)
     dst
     (recur (cons x dst) x (- n 1))))
 
 (defn skip-eq [lst x]
   (if (or (empty? lst) (not (= (first lst) x)))
     lst
     (recur (rest lst) x)))
 
 (defn selection-sort2 [lst tmp prev]
   (let [
       tail (skip-eq lst prev)
       that (find-next tail prev nil 0)
       x (:x that)]
     (if (nil? x)
       tmp
       (recur tail (dup-list tmp x (:n that)) x))))
 
 (defn selection-sort [lst]
   (let [that (find-largest lst) x (:x that)]
     (selection-sort2 lst (dup-list [] x (:n that)) x)))
 
 ; Test
 (selection-sort [1 2 3 4 5 9 11 5 1 4 7 2 1 0 0 11])