Функция сравнения как параметр в ракетке - PullRequest
Новая
       23

Функция сравнения как параметр в ракетке

0 голосов
/ 26 марта 2020

Я реализовал сортировку выбора в Racket следующим образом: 

#lang racket
(define (selection-sort lst)
  (cond [(empty? lst) '()]
        [else (define first (apply min lst))
              (cons first (selection-sort(remove first lst)))]))

(selection-sort (list 5 4 3))

Однако меня просят, чтобы моя функция принимала функцию сравнения вместе со списком, и сортировка выбора должна возвращать список по возрастанию заказ в соответствии с функцией сравнения.

У меня проблемы с пониманием этого бита с помощью функции сравнения, что мне нужно изменить в коде?

1 Ответ

2 голосов
/ 26 марта 2020

Имейте в виду, что текущая реализация довольно неэффективна, вы делаете там много дополнительных циклов: при поиске минимума, при его удалении.

Сказав это, мы можем адаптировать код чтобы получить функцию сравнения, написав наш собственный min, который получает произвольную функцию сравнения - потому что неявно min использовал <. Вот так: 

(define (selection-sort lst cmp)
  (cond [(empty? lst) '()]
        [else (define amin (mymin cmp lst))
              (cons amin (selection-sort (remove amin lst) cmp))]))

(define (mymin cmp lst)
  ; assuming non-empty list
  (cond [(empty? (rest lst))
         (first lst)]
        ; call the recursion
        [else (define amin (mymin cmp (rest lst)))
              ; use the comparison function
              (cond [(cmp (first lst) amin) (first lst)]
                    [else amin])]))

Работает как положено: 

; ascending order, this was the default behavior
(selection-sort (list 5 4 3) <)
=> '(3 4 5)
; same as above
(selection-sort (list 5 4 3) (lambda (x y) (< x y)))
=> '(3 4 5)
; descending order
(selection-sort (list 5 4 3) >)
=> '(5 4 3)
...