# Ordered list in Scheme

This topic is 4492 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone, I've been fiddling around wracking my brain for a while... trying to work out how to order a list. Now I've been thinking of different algorithms. But I have failed. Yes I know, laugh it up. lol But I have created some code.. don't laugh.. i know it doesn't make sense. But I was wondering if you could help me with my understanding of an algorithm. (i don't want code cus i can do code) I just want to know how to order it. Because I have realised that the ordering part of things is very important.. eg: excel uses the A->Z thingie in the tables lol. Ordering is just a tad difficult. Please help. (not with code.. just understanding). thanks in advance (define [quicksort list1] (the-quicksort list1 (first list1) empty)) (define [the-quicksort list1 first1 other] (cond [(empty? list1) other] [(<= (first list1) first1) (the-quicksort (rest list1) first1 (cons (first list1) other))] [else (the-quicksort (rest list1) first1 (cons (first list1) other))] ) )

##### Share on other sites
quicksort  sourceList:   split sourceList into two parts (resLess, resGrEq),      which contain, accordingly, elements (<) and (>=) to (first sourceList)      do not put (first sourceList) on any of them! (might lead to infinite recursion)   append (resLess, (first sourceList), resGrEq);q-split2 sourceList destLess destGrEq cmp   if (empty? sourceList)      call quicksort on destLess      call quicksort on destGrEq      return (destLess, destGrEq)   else if ((first sourceList) < cmp)      put (first sourceList) on destLess and call q-split2 with tail recursion   else      put (first sourceList) on destGrEq and call q-split2 with tail recursion;

This is only pseudo-code, just as you wanted.

Good luck!
~def

##### Share on other sites
What quicksort does is split the ordering problem recursively into subproblems. That is, given a list of numbers, it chooses one of the numbers to use as a pivot, and splits the list along that number.

So if you´ve got a list called LIST, the quicksort chooses a pivot number and splits the list into three components:

1) LIST-LESS-THAN-OR-EQUAL: The elements in the original LIST that are less than or equal to your pivot number.

2) pivot: The number you´ve chosen as your pivot point.

3) LIST-GREATER-THAN: The numbers in your list that are greater than your pivot.

Notice that this is true now:

LIST-LESS-THAN-OR-EQUAL <
(define (filter pred? alist)  (if (null? alist) '()      (if (pred? (car alist)) (cons (car alist) (filter pred? (cdr alist)))          (filter pred? (cdr alist)))))(define (qsort alist)  (if (null? alist) '()      (let* ((pivot (car alist))             (the-rest (cdr alist))             (lt-or-equal (filter (lambda (x) (<= x pivot)) the-rest))             (gt (filter (lambda (x) (> x pivot)) the-rest)))        (append (qsort lt-or-equal) (list pivot) (qsort gt))))); for example> (qsort '())()> (qsort '(1))(1)> (qsort '(3 5 7 9 9 6 3 3))(3 3 3 5 6 7 9 9)

##### Share on other sites
Argh, the forum ate part of my post.

Notice that this is true now:

LIST-LESS-THAN-OR-EQUAL is less than PIVOT is less than LIST-GREATER-THAN

So all you need to do is apply the recursion to the end, and concatenate the lists in that order as you go:

qsort(LIST-LESS-THAN-OR-EQUAL) + pivot + qsort(LIST-GREATER-THAN) ** This is exactly what I do in the example scheme program

And voilà, an ordered list. Don't be discouraged if you didn't come up with this on your own: bright people have put lots of thought into the sorting problem.

Remember, work out your algorithm BEFORE you start randomly writing code.

Above is a scheme version that does exactly what I described above: it is not efficient (uses append), but is VERY clear. It is the explanation above only rewritten in scheme. I choose the first number in the list as the pivot point for simplicity. I also define the filter auxiliary function, which just takes a list and a predicate and returns the list of elements that satisfy the predicate.

If it's not clear, the-rest is the list of numbers minus the pivot, lt-or-equal stands for the elements that are less than or equal to the pivot, and gt for the elements that are strictly greater than th

##### Share on other sites
sorry, what is cmp?
lol

##### Share on other sites
Hmm I am still confused.
Is it possible to post a line of code.. eg the recursive tail section for <=, or <?.
If I see that (not in the confusing scheme language you used hahaha).. then i'll be like "oooh i see how it works.." and then will be able to write the algorithm and then the code.

for some reason, seeing a line of code explains everything.. or maybe it is just that i am tired?
:S

it kinda gives me a flash of the whole process i guess lol
Eg. like the code that i showed before.. i'd past this
[(<= (first list1) first1)
(the-quicksort (rest list1) first1 (cons (first list1) other))]

Or even a written version of what happens to each component.. i'm just confused at the overall picture of things. I tried to imagine each thing going in a "box"... and i had 2 boxes.. now millions poppin outta my ears. :S

##### Share on other sites
Quote:
 Original post by Anonymous Postersorry, what is cmp?lol

The chosen element with regard to we're doing the split.
Here:
(first sourceList)

##### Share on other sites
Quote:
 Original post by petemurrayHmm I am still confused.Is it possible to post a line of code.. eg the recursive tail section for <=, or

// returns pair (lessList, greqList)(define (split source elem)   (split2 source elem nil nil))(define (split2 source elem lessList greqList)   (cond      (  (empty? source)         (cons lessList greqList)) // return pair (lessList, greqList)      (  (< elem (first source))         (split2 (rest source) // move first value from source to lessList                 elem                 (cons (first source) lessList)                 greqList) )      // else         (split2 (rest source) // move first value from source to greqList                 elem                 lessList                 (cons (first source) greqList) )    ))

##### Share on other sites
Quote:
 If I see that (not in the confusing scheme language you used hahaha).. then i'll be like "oooh i see how it works.."

The 'confusing scheme language' I used IS VALID, WORKING SCHEME CODE. Cut and paste it into Dr. Scheme and run it if you want to check.

I posted an explanation and a complete, working solution in vanilla scheme. How about you try to understand that (it's as simple as it gets) before asking for more help?

##### Share on other sites
I have done this.. (not very much though)

(define [split source]
(split2 source (first source) empty empty))

(define [split2 source elem lessList greqList]
(cond [(empty? source)
(cons lessList greqList)]
[(< elem (first source))
(split2 (rest source)
elem
(cons (first source) lessList)
greqList)]
[else
(split2 (rest source)
elem
lessList
(cons (first source) greqList))]
))

At the moment, it is separating the components i.e
(split (list -2 20 100 -5 20))
Gives: (list (list 20 100 20) -5 -2)

This is where I am confused.. how to make this process continue...
As the first of the list is a list, not a number, thus this causes an error.

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
14

• 14
• 10
• 23
• 9
• 33
• ### Forum Statistics

• Total Topics
632631
• Total Posts
3007536
• ### Who's Online (See full list)

There are no registered users currently online

×