fork download
copy 
  1. ;; Генерация последовательности Седжвика
  2. (defun sedgewick-sequence (n)
  3.   (labels ((sedgewick-iter (k seq)
  4.              (let ((next (+ (* 4 (expt 2 k)) (* 3 (expt 2 (1- k))) 1)))
  5.                (if (> next n)
  6.                    (reverse seq)
  7.                    (sedgewick-iter (1+ k) (cons next seq))))))
  8.     (if (<= n 1)
  9.         '(1)
  10.         (sedgewick-iter 1 '(1)))))
  11.  
  12. ;; Сортировка вставками с заданным шагом
  13. (defun insertion-sort-step (lst step cmp)
  14.   (let ((n (length lst)))
  15.     (loop for i from step below n
  16.           do (let ((temp (nth i lst))
  17.                    (j i))
  18.                (loop while (and (>= j step) (funcall cmp temp (nth (- j step) lst)))
  19.                      do (setf (nth j lst) (nth (- j step) lst))
  20.                         (decf j step))
  21.                (setf (nth j lst) temp))))
  22.   lst)
  23.  
  24. ;; Основная функция сортировки Шелла
  25. (defun shell-sort (lst cmp)
  26.   (let ((n (length lst)))
  27.     (if (<= n 1)
  28.         lst
  29.         (let ((steps (sedgewick-sequence n)))
  30.           (shell-sort-with-steps lst steps cmp)))))
  31.  
  32. ;; Сортировка с последовательностью шагов
  33. (defun shell-sort-with-steps (lst steps cmp)
  34.   (if (null steps)
  35.       lst
  36.       (shell-sort-with-steps
  37.        (insertion-sort-step lst (car steps) cmp)
  38.        (cdr steps)
  39.        cmp)))
  40.  
  41. ;; Примеры использования
  42.  
  43. ;; Сортировка списка чисел по возрастанию
  44. (let ((numbers '(5 2 8 1 9 4 0 7 3 6)))
  45.   (format t "Original list: ~a~%" numbers)
  46.   (let ((sorted-numbers (shell-sort (copy-list numbers) #'<))) 
  47.     (format t "Sorted list: ~a~%" sorted-numbers)))
  48.  
  49.  
Success #stdin #stdout #stderr 0.02s 9524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original list: (5 2 8 1 9 4 0 7 3 6)
Sorted list: (0 1 2 3 4 5 6 7 8 9)
stderr
copy 
Warning: reserving address range 0x80000c0000...0x1fffffffffff that contains memory mappings. clisp might crash later!
Memory dump:
  0x8000000000 - 0x80000bffff
  0x15420f600000 - 0x15420f8e4fff
  0x15420fa15000 - 0x15420fa39fff
  0x15420fa3a000 - 0x15420fbacfff
  0x15420fbad000 - 0x15420fbf5fff
  0x15420fbf6000 - 0x15420fbf8fff
  0x15420fbf9000 - 0x15420fbfbfff
  0x15420fbfc000 - 0x15420fbfffff
  0x15420fc00000 - 0x15420fc02fff
  0x15420fc03000 - 0x15420fe01fff
  0x15420fe02000 - 0x15420fe02fff
  0x15420fe03000 - 0x15420fe03fff
  0x15420fe80000 - 0x15420fe8ffff
  0x15420fe90000 - 0x15420fec3fff
  0x15420fec4000 - 0x15420fffafff
  0x15420fffb000 - 0x15420fffbfff
  0x15420fffc000 - 0x15420fffefff
  0x15420ffff000 - 0x15420fffffff
  0x154210000000 - 0x154210003fff
  0x154210004000 - 0x154210203fff
  0x154210204000 - 0x154210204fff
  0x154210205000 - 0x154210205fff
  0x15421037d000 - 0x154210380fff
  0x154210381000 - 0x154210381fff
  0x154210382000 - 0x154210383fff
  0x154210384000 - 0x154210384fff
  0x154210385000 - 0x154210385fff
  0x154210386000 - 0x154210386fff
  0x154210387000 - 0x154210394fff
  0x154210395000 - 0x1542103a2fff
  0x1542103a3000 - 0x1542103affff
  0x1542103b0000 - 0x1542103b3fff
  0x1542103b4000 - 0x1542103b4fff
  0x1542103b5000 - 0x1542103b5fff
  0x1542103b6000 - 0x1542103bbfff
  0x1542103bc000 - 0x1542103bdfff
  0x1542103be000 - 0x1542103befff
  0x1542103bf000 - 0x1542103bffff
  0x1542103c0000 - 0x1542103c0fff
  0x1542103c1000 - 0x1542103eefff
  0x1542103ef000 - 0x1542103fdfff
  0x1542103fe000 - 0x1542104a3fff
  0x1542104a4000 - 0x15421053afff
  0x15421053b000 - 0x15421053bfff
  0x15421053c000 - 0x15421053cfff
  0x15421053d000 - 0x154210550fff
  0x154210551000 - 0x154210578fff
  0x154210579000 - 0x154210582fff
  0x154210583000 - 0x154210584fff
  0x154210585000 - 0x15421058afff
  0x15421058b000 - 0x15421058dfff
  0x154210590000 - 0x154210590fff
  0x154210591000 - 0x154210591fff
  0x154210592000 - 0x154210592fff
  0x154210593000 - 0x154210593fff
  0x154210594000 - 0x154210594fff
  0x154210595000 - 0x15421059bfff
  0x15421059c000 - 0x15421059efff
  0x15421059f000 - 0x15421059ffff
  0x1542105a0000 - 0x1542105c0fff
  0x1542105c1000 - 0x1542105c8fff
  0x1542105c9000 - 0x1542105c9fff
  0x1542105ca000 - 0x1542105cafff
  0x1542105cb000 - 0x1542105cbfff
  0x5641ab4d3000 - 0x5641ab5c3fff
  0x5641ab5c4000 - 0x5641ab6cdfff
  0x5641ab6ce000 - 0x5641ab72dfff
  0x5641ab72f000 - 0x5641ab75dfff
  0x5641ab75e000 - 0x5641ab78efff
  0x5641ab78f000 - 0x5641ab792fff
  0x5641ac9b1000 - 0x5641ac9d1fff
  0x7fff12296000 - 0x7fff122b6fff
  0x7fff122eb000 - 0x7fff122eefff
  0x7fff122ef000 - 0x7fff122f0fff
https://ideone.com/Nfxoy2
language:
Common Lisp (clisp 2.49.92)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!