; Удаление из списка элемента с заданным номером

(define (delete_element_by_number curr_number lst)
  (cond
   ((= curr_number 1) (rest lst))
   (true (cons (first lst) (delete_element_by_number (- curr_number
       1)
      (rest lst))))))

; Поиск элемента по заданному номеру

(define (find_element_by_number num lst)
  (cond
   ((= num 1) (first lst))
   (true (find_element_by_number (- num 1) (rest lst)))))

; Формирование списка элементов, отстоящих друг от друга на заданное
; расстояние

(define (group_build lst lst_len step curr_number)
  (cond
   ((> curr_number lst_len) '())
   (true (sifting (find_element_by_number curr_number lst) (group_build
      lst lst_len step
      (+ curr_number step))))))

; Группировка элементов, отстоящих друг от друга на заданное расстояние

(define (grouping lst lst_len step curr_elem_number)
  (cond
   ((> curr_elem_number step) '())
   (true (cons (group_build lst lst_len step curr_elem_number) (grouping
      lst lst_len step
      (+ curr_elem_number 1))))))

; Запуск процедуры вставки списка в список

(define (insert_list_to_list lst1 step lst2)
  (insert_list_to_list_step_n lst1 step 1 lst2))

; Вставка элементов одного списка в другой с заданным интервалом

(define (insert_list_to_list_step_n lst step cnt ins_list)
  (cond
   ((null? lst) ins_list)
   ((null? ins_list) lst)
   ((< cnt step) (cons (first lst) (insert_list_to_list_step_n (rest
       lst) step
      (+ cnt 1) ins_list)))
   ((= step cnt) (cons (first lst) (cons (first ins_list) (insert_list_to_list_step_n
       (rest lst) step 1
       (rest ins_list)))))))

; Запуск процедуры вставки списка в список

(define (insert_lists_to_list lst_arg group_list)
  (insert_lists_to_list_start lst_arg 1 group_list))

; Вставка элементов списков в список с изменяющимся шагом

(define (insert_lists_to_list_start lst_arg step group_list)
  (cond
   ((null? group_list) lst_arg)
   (true (insert_lists_to_list_start (insert_list_to_list lst_arg
      step
      (first group_list))
     (+ step 1)
     (rest group_list)))))

; Проход сортировки Шелла для заданного шага

(define (one_prohod lst lst_len step)
  (append (insert_lists_to_list (first (grouping lst lst_len step
      1))
    (rest (grouping lst lst_len step 1)))
   (rest_of_list_from_nth_to_end lst (length (insert_lists_to_list
      (first (grouping lst lst_len step 1))
      (rest (grouping lst lst_len step 1)))))))

; Удаление из исходного списка элементов, отстоящих друг от друга на заданное
; расстояние

(define (rest_of_list lst lst_len step curr_number)
  (cond
   ((> curr_number lst_len) lst)
   (true (rest_of_list (delete_element_by_number curr_number lst)
     (- lst_len 1) step
     (- (+ curr_number step) 1)))))

; Выделение в список всех элементов, начиная с (n+1)-го

(define (rest_of_list_from_nth_to_end lst n)
  (cond
   ((= n 1) (rest lst))
   (true (rest_of_list_from_nth_to_end (rest lst) (- n 1)))))

; Выполнение сортировки Шелла для заданного списка шагов

(define (shell_sort lst lst_len step_list)
  (cond
   ((null? step_list) lst)
   (true (shell_sort (one_prohod lst lst_len (first step_list)) lst_len
     (rest step_list)))))

; Запуск сортировки Шелла

(define (shell_sort_start lst)
  (shell_sort lst (length lst) (my_reverse (steplist (length lst) 0))))

; Вставка элемента в список путем просеивания

(define (sifting elem lst)
  (cond
   ((null? lst) (cons elem '()))
   ((<= elem (first lst)) (cons elem lst))
   (true (cons (first lst) (sifting elem (rest lst))))))

; Сортировка списка просеиванием

(define (sifting_sort lst)
  (cond
   ((null? lst) '())
   (true (sifting (first lst) (sifting_sort (rest lst))))))

; Формирование списка шагов

(define (steplist length_of_list s)
  (cond
   ((and (> (mod s 2) 0) (<= (* 3 (+ 1 (- (* 8 (pow 2 s)) (* 6 (pow
           2
           (/ (+ s 1) 2)))))) length_of_list))
    (cons (+ 1 (- (* 8 (pow 2 s)) (* 6 (pow 2 (/ (+ s 1) 2))))) (
      steplist length_of_list
      (+ s 1))))
   ((and (= (mod s 2) 0) (<= (* 3 (+ 1 (- (* 9 (pow 2 s)) (* 9 (pow
           2
           (/ s 2)))))) length_of_list))
    (cons (+ 1 (- (* 9 (pow 2 s)) (* 9 (pow 2 (/ s 2))))) (steplist
      length_of_list
      (+ s 1))))
   ((and (> (mod s 2) 0) (> (* 3 (+ 1 (- (* 8 (pow 2 s)) (* 6 (pow
           2
           (/ (+ s 1) 2)))))) length_of_list)) '())
   ((and (= (mod s 2) 0) (> (* 3 (+ 1 (- (* 9 (pow 2 s)) (* 9 (pow
           2
           (/ s 2)))))) length_of_list)) '())))

; реверсирование

(define (my_rev lst1 lst2)
 (cond
       ((null? lst1) lst2)
       (true (my_rev (rest lst1) (cons (first lst1) lst2)))
 )
)
(define (my_reverse lst)
 (my_rev lst '())
)