(defmacro puts (line)
  `(format t "~s~%" ,line))

(defun frontOfArray (array i)
  (butlast array (- (length array) i)))

(defun middleOfArray (array i j)
  (endOfArray (frontOfArray array j) i))

(defun endOfArray (array j)
  (last array (- (length array) (+ j 1))))

(defun swap (array i j)
  (concatenate 'list
	       (frontOfArray array i)
	       `(,(nth j array))
	       (middleOfArray array i j)
	       `(,(nth i array))
	       (endOfArray array j)))

(defun swapNeeded (array i j)
  (if (> (nth i array) (nth j array))
      t
    nil))

(defun swapIfNeeded (array i j)
  (if (swapNeeded array i j)
      (swap array i j)
    array))

(defun gapCalc (gap)
  (floor (/ (* gap 10) 13)))

(defun newGap (gap)
  (if (< (gapCalc gap) 1) 1 (gapCalc gap)))

(defun sortWithGap (index array gap)
  (if (= index (- (length array) gap))
      array
    (sortWithGap (+ index 1) (swapIfNeeded array index (+ index gap)) gap)))

(defun detectEndOfSort (oldarray newarray gap)
  (if (and (equalp oldarray newarray) (= gap 1))
      newarray
    (startNewGap newarray (newgap gap))))

(defun startNewGap (array gap)
  (detectEndOfSort array (sortWithGap 0 array gap) gap))

(defun combsort (array)
  (startNewGap array (newGap (length array))))

(defun runArray (array)
  (puts array)
  (puts (combsort array)))

(runArray '(1 6 5 3 8 6 9 7 2 4 0))