Using quicksort to sort arbitrary lists

The quicksort function consumes a list and a less-than comparison function and produces an ordered list in which elements are arranged into ascending order. For example:

(quicksort '(1 5 3 8 7 2) <) => '(1 2 3 5 7 8)

Write a comparison function that can be used by quicksort to compare elements of a list according to the following rules:

• Two numbers should be compared using < (less than).
• Two strings should be compared using string<?
• Two symbols should be compared by converting the symbols to strings (with symbol->string) and then using string<?
• All numbers are less than all strings or symbols
• All strings are less than all symbols.

Test your function with quicksort to sort the following list:

(define l1 '(1000 22 Fred "Hello World" 33 Sally "PSICS" 1024))
;; should end up as (list 22 33 1000 1024 "Hello World" "PSICS" 'Fred 'Sally)

---

Universal sort function

Write a universal sorting function that can sort lists of numbers, or lists of symbols, or lists of strings. Feel free to use quicksort to do the sorting for you (you may also use your code from the previous question). Name the function usort and test it out with the following:

(usort '(1 8 2 9 33 26 3 22 7 45 100))

(usort '(seven two one three eight twelve))

(usort '("Hello" "World" "Scheme" "is" "fun"))

---

Function Generalization

Consider the two functions shown below:

;;
;; remove-duplicate-symbols consumes a list of symbols and produces
;;  a list of symbols
;;
;; (remove-duplicate-symbols alos) produces a list of the symbols
;;   found in the list alos, with all duplicates removed.
;;
;; (remove-duplicate-symbols '(Sally Fred George Sally Sam Fred Sally Sally))
;;
(define (remove-duplicate-symbols alos)
  (local
   ((define (remove-symbol-from-list alos x)
        (cond
           [(empty? alos) empty]
           [(symbol=? x (first alos))
                (remove-symbol-from-list (rest alos) x)]
           [else
                (cons (first alos) (remove-symbol-from-list (rest
		alos) x))])))
  (cond
   [(empty? alos) empty]
   [else
        (cons (first alos)
                  (remove-duplicate-symbols
                   (remove-symbol-from-list (rest alos) (first
		   alos))))])))
 
;; test code
(remove-duplicate-symbols '(Sally Fred George Sally Sam Fred Sally Sally))

;;
;; remove-duplicate-numbers consumes a list of numbers and produces
;;  a list of numbers
;;
;; (remove-duplicate-numbers alon) produces a list of the numbers
;;   found in the list alon, with all duplicates removed.
;;
;; usage: (remove-duplicate-numbers '(1 2 3 1 2 3 1 2 3 4 5 4 ))
;;
(define (remove-duplicate-numbers alon)
  (local
   ;; remove-number-from-list removes all occurrences of x from
   ;; the list alon.
   ((define (remove-number-from-list alon x)
          (cond
           [(empty? alon) empty]
           [(= x (first alon))
                (remove-number-from-list (rest alon) x)]
           [else
                (cons (first alon) (remove-number-from-list (rest alon) x))])))
 
  (cond
   [(empty? alon) empty]
   [else
        (cons (first alon)
                  (remove-duplicate-numbers
                   (remove-number-from-list (rest alon) (first alon))))])))
 
;; test code
(remove-duplicate-numbers '(1 2 3 1 2 3 1 2 3 4 5 4 ))

Generalize the functions and create a single function that includes a parameter that is a function/operator that is used to determine whether two list elements are the same. Assuming you name your function remove-duplicates, it could then be used like this:

(remove-duplicates '(Sally Fred George Sally Sam Fred Sally Sally) symbol=? )

(remove-duplicates '(1 2 3 1 2 3 1 2 3 4 5 4 ) = )

---

Another operator for remove-duplicates

Write a new operator or find an existing operator that will allow you to use remove-duplicates to operate on mixed lists. For example:

(remove-duplicates '(1 Sally 2 Fred 3 George 1 2 3 Sam 4 Fred 5 Sally 2 Sally 4) newop ) =>
(list 1 'Sally 2 'Fred 3 'George 'Sam 4 5)