Sorting a 2d-vector by index value into lazy sequence in clojure

Question

I am reading the Joy Of Clojure and came across an implementation of quick sort that uses lazy sequences to achieve better than O(n log n) performance when only taking the first few cons cells from the lazy sequence. I am trying to get it to work for a 2d array of integers, but I can't quite seem to get it: So far this is what I have:

(defn sort-parts2
  "Lazy, tail-recursive, incremental quicksort. Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
    (loop [[part & parts] work]
      (if-let [[pivot & xs] (seq part)]
        (let [smaller? #(< % pivot)]
          (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
      (when-let [[x & parts] parts] 
      (cons x (sort-parts2 parts)))))))



   sort.joy=> a
    [[5 9 0 6 5 1 4 4 8 7]
     [2 6 8 2 6 7 0 1 8 1]
     [8 8 0 5 9 9 7 7 1 6]
     [9 8 5 3 0 2 0 6 9 3]
     [8 8 5 8 9 8 2 3 8 5]
     [7 9 2 8 5 6 6 8 3 4]
     [4 8 2 4 6 6 7 4 4 1]
     [8 5 1 7 3 0 2 4 2 3]
     [9 1 2 9 0 1 0 2 2 9]
     [4 0 2 6 8 5 6 1 7 7]]

what I want to get for an input of (sort-parts2 a 0) //index on the first element of the subvectors is:

   sort.joy=> aSorted
     [[2 6 8 2 6 7 0 1 8 1]
     [4 0 2 6 8 5 6 1 7 7]
     [4 8 2 4 6 6 7 4 4 1]
     [5 9 0 6 5 1 4 4 8 7]
     [7 9 2 8 5 6 6 8 3 4]
     [8 5 1 7 3 0 2 4 2 3]
     [8 8 0 5 9 9 7 7 1 6]
     [8 8 5 8 9 8 2 3 8 5]
     [9 1 2 9 0 1 0 2 2 9]
     [9 8 5 3 0 2 0 6 9 3]]

as is, this is what I am getting right now:

sort.joy=> (sort-parts a)
(0
 1
 4
 4
 5
 5
 6
 7
 8
 9
 [2 6 8 2 6 7 0 1 8 1]
 0
 1
 5
 6
 7
 7
 8
 8
 9
 9
 [9 8 5 3 0 2 0 6 9 3]
 2
 3
 5
 5
 8
 8
 8
 8
 8
 9
 [7 9 2 8 5 6 6 8 3 4]
 1
 2
 4
 4
 4
 4
 6
 6
 7
 8
 [8 5 1 7 3 0 2 4 2 3]
 0
 0
 1
 1
 2
 2
 2
 9
 9
 9
 [4 0 2 6 8 5 6 1 7 7])

Could someone please help me figure out a way to stop the loop from fully destructuring the 2d vector, thus returning a lazy vector with the head being a row vector? I have the comparotors for the rows figured out, thank you!

edit More general formulation of the problem: I want to sort a 2d vector, seen as a bellow into a lazy-sequence, where the head is the next sub-vector ordered by an index. To do this non-lazily, I am using:

(defn sortVector 
  "sorts a 2d vector by the given index"
  [index coll]
  (sort-by #(nth % index) coll))

Michał Marczyk Michał Marczyk · Accepted Answer · 2012-01-20T18:53:50

You can derive a sort-parts-by function from the JoC code if you start off with the original and replace the smaller? function with one which compares the values of some key function on pivot and another item, rather than the items directly:

(let [pivot-key (keyfn pivot)
      smaller? #(.compare ^java.util.Comparator comp
                          (keyfn %1)
                          pivot-key)]
  ...)

The names keyfn and comp come from clojure.core/sort-by -- see its docstring / implementation for the intended meaning.

Note that sort-parts is not intended to be called on the actual sequence to be sorted -- you have to wrap it in some sort of seqable first (probably a vector); see the definition of qsort in JoC for an example. You'll probably want a qsort-by to go along with the function sketched above.

Sorting a 2d-vector by index value into lazy sequence in clojure

1 Answers