[Solved]: Variation on Insertion Sort

Problem Detail: 

I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the "find lowest" or inner loop.

I'll reproduce the algorithm here in Python (aka the universal psuedocode) to explain. I'll also use iteration so it's easier to understand.

def insertion_sort(list):   for i in range(len(list)):     for j in range(i + 1, len(list)):       if list[j] < list[j]:         list[i], list[j] = list[j], list[i] 

The difference is that I repeatedly swap the old lowest with new lowest numbers as they're found, and reinsert the old lowest back into the list where the new lowest was.

Can I still (correctly) refer to this as insertion sort and is there a significant effect on efficiency?

Also, just in case there's anyone here who loves scheme:

(define lowest-to-front-helper   (lambda (list lowest)     (if (eq? (cdr list) '())         (if (>= (car list) lowest)             (cons lowest list)             (cons (car list)                   (cons lowest '())))         (if (< (car list) lowest)             (let ((temp (lowest-to-front-helper (cons lowest (cdr list)) (car list))))               (cons (car temp)                     (cdr temp)))             (let ((temp (lowest-to-front-helper (cdr list) lowest)))               (cons (car temp)                     (cons (car list) (cdr temp))))))))  ; Permutes list such that the lowest element is moved to the front. (Non-stable.) (define lowest-to-front   (lambda (list)     (lowest-to-front-helper (cdr list) (car list))))  (define insertion-sort   (lambda (list)     (if (eq? (cdr list) '())         list         (let ((temp (lowest-to-front list)))           (cons (car temp) (insertion-sort (cdr temp))))))) 

Asked By : Tyler

Answered By : Louis

Insertion sort maintains the following loop invariant:

• After iteration $i$, the first $i$ positions in the array are the first $i$ positions of the input, in sorted order

Note that this doesn't mean that they need to be in their final positions for the sort to work at the end. I'd say that this is the defining thing for "insertion sort", but that's not really a formal statement.

Insertion sort is not hard to turn into a recursive procedure. The main routine you want is a helper called insert-sorted such that consumes a sorted list and a number, and outputs a new sorted list (one longer) that includes the number. You can write it in a way that is pretty much paradigmatic for Scheme (note, code just typed in, not tried):

(define (insert-sorted n l le)     (if (null? l)         (list n)         (if (le n (car l))             (cons n l)             (cons (car l) (insert-sorted n (cdr l) le))))) 

In words, if n comes before the first element of l or l is empty, then n goes in first position. Otherwise, the list we want starts with the first element of l and ends with n in the right place in the tail of l.

With the helper, involves repeatedly calling insert-sorted to build up the sorted list. If you want to follow the invariant exactly, then an approach like this will work:

(define (insertion-sort l le)     (define (rec s l)         (if (null? l) s (rec (insert-sorted (car l) s le) (cdr l))))     (rec '() l)) 

However, this solution explicitly maintains s, the partially sorted list. More idiomatic scheme would be to just use the call stack for this:

(define (insertion-sort l le)     (if (null? l)         '()          (insert-sorted (car l) (insertion-sort (cdr l) le) le))) 

I'll leave it to you to work out what the invariant for each implementation is.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41810

3.2K people like this

 Download Related Notes/Documents