   Ordered list in Scheme
  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. lolBut 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 <(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);  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-THANSo 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 programAnd 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?:Sit kinda gives me a flash of the whole process i guess lolEg. 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 Postersorry, what is cmp?lolThe chosen element with regard to we're doing the split.Here:(first sourceList)   ;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) )    ));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.   