cperilla

10/25/2013 - 6:59 PM

Slow sort, pessimal algorithms and simplexity analysis

```
;; scheme: chicken scheme
;; Author: Carlos Perilla <deepspawn AT valkertown.org>
;; Date: 25-10-2013
;; http://programmingpraxis.com/2013/10/25/pessimal-algorithms-and-simplexity-analysis/
;; The slowsort algorithm is a perfect illustration of the multiply
;; and surrender paradigm, which is perhaps the single most important
;; paradigm in the development of reluctant algorithms. The basic
;; multiply and surrender strategy consists in replacing the problem at
;; hand by two or more subproblems, each slightly simpler than the
;; original, and continue multiplying subproblems and subsubproblems
;; recursively in this fashion as long as possible. At some point the
;; subproblems will all become so simple that their solution can no
;; longer be postponed, and we will have to surrender. Experience shows
;; that, in most cases, by the time this point is reached the total work
;; will be substantially higher than what could have been wasted by a
;; more direct approach.
;; To get a ﬁrmer grasp of the multiply and surrender method, let us
;; follow the step-by-step development of the slowsort algorithm. We can
;; decompose the problem of sorting n numbers Al, A2, …, An in ascending
;; order into (1) ﬁnding the maximum of those numbers, and (2) sorting
;; the remaining ones. Subproblem (1) can be further decomposed
;; into (1.1) ﬁnd the maximum of the ﬁrst [n/2] elements, (1.2) ﬁnd the
;; maximum of the remaining [n/2] elements, and (1.3) ﬁnd the largest of
;; those two maxima. Finally, subproblems (1.1) and (1.2) can be solved
;; by sorting the speciﬁed elements and taking the last element in the
;; result. We have thus multiplied the original problem into three
;; slightly simpler ones (sort the ﬁrst half, sort the second half, sort
;; all elements but one), plus some overhead processing. We continue
;; doing this recursively until the lists have at most one element each,
;; at which point we are forced to surrender.
(use srfi-1)
(define (split lst)
(let ((half (quotient (length lst) 2)))
(list (take lst half)
(drop lst half))))
(define sample-list '(239 495 631 786 853 750 886 457 784 449 584 47
885 514 731 772 249 239 1000 731))
(define (slowsort inputlist)
(if (null? inputlist) inputlist
(let [(max (slowmax inputlist))]
(reverse (cons max (reverse (slowsort (delete max inputlist))))))))
(define (slowmax inputlist)
(if (null? (cdr inputlist))
(car inputlist)
(let* [(halves (split inputlist))
(first-half (car (reverse (slowsort (car halves)))))
(second-half (car (reverse (slowsort (cadr halves)))))]
(if (> first-half second-half) first-half second-half))))
(slowsort sample-list)
```