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

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

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 <

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

sorry, what is cmp?
lol

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

Quote:Original post by Anonymous Poster
sorry, what is cmp?
lol

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

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 <?.

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?

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.