Sign in to follow this  
petemurray

Ordered list in Scheme

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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by petemurray
Hmm 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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by petemurray
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)


Actually, it's:
(cons (list 20 100 20) (list -5 -2))
which is exactly the same, it's just Dr.Scheme's interpreter that confuses matter.

Now sort each part recursively and merge the outputs.

Share this post


Link to post
Share on other sites
Nothing seems to be working for me.
I just can't see the overall picture of how it works.

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

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


I change elem to first source in the recursive tail part.
THought it worked at first...

(split (list -2 50 3))
gave me the result (50 3 -2)
and reversing it... (-2 3 50).

But no :(... more tests proved that it doesn't work. *sob*
i just can't see how to do it. and i thought i was getting the hang of things.. :(

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer

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);



I don't know how else I can put it.
In my oppinion, you should be able to get it from this description, especially that I already provided you with splitting routine.

Also, AP has already posted full working version, so I think it's time you think it out on your own.

Good luck!
~def

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this