|
 |
Hi there programming gurus.
I'm searching for sorting algorithm description in pseudo-code ("take
the first element, compare it with this, put it there...") not code
examples (wich I found plenty but they are
usless to me.
Where in the Net can I find them.
I'm expecially interested in quicksort and mergesort.
It's for a POV related 3D tool I'm developing.
Thank you in advance
(---------------------------------------------------------------)
( Diego Krota http://www.geocities.com/SiliconValley/Way/2419 )
(---------------------------------------------------------------)
( Never do anything you wouldn't be caught dead doing )
(---------------------------------------------------------------)
Post a reply to this message
|
|
|
|
On Thu, 19 Nov 1998 21:38:58 +0200, Diego Krota <Xdk### [at] geocities com> wrote:
>I'm searching for sorting algorithm description in pseudo-code ("take
>the first element, compare it with this, put it there...") not code
>examples (wich I found plenty but they are
>usless to me.
>Where in the Net can I find them.
>I'm expecially interested in quicksort and mergesort.
>
>It's for a POV related 3D tool I'm developing.
That doesn't really make it on-topic, but okay. First, if you're using C or
C++, look at the qsort() function.
To do a quicksort, pick an element from the list of items to be sorted. This
is the "pivot" element. Do whatever is necessary to put all elements less than
the pivot element to the left, and all elements greater to the right. Now you
have two subarrays, one of lesser elements and one of greater elements, and the
pivot element is in the right place. Run quicksort on each of those subarrays.
Note that Quicksort is really slow when you run it on an already-sorted list.
1. If there are zero or one elements in the list, stop.
2. Pick the first element as your pivot.
3. Set up a pointer to the left end of the unsorted part. This should be the
second element. Call it L.
4. Set up a pointer to the right end. This should be the last element. Call
it R.
5. Move L to the right until it points to an item that's greater than the pivot
or it falls off the end of the list.
6. Move R to the left until it points to an item that's less than the pivot or
it falls off the beginning of the list.
7. If R and L are still in the list, and R is still to the right of L, swap
the items pointed to by L and R and repeat from step 5.
8. If R has fallen off the beginning of the array, there are no items less
than the pivot so it is in the right place. In that case, quicksort the
right sublist and stop; there is no left sublist.
9. If you got this far, swap the item pointed to by R (which is less than the
pivot) with the pivot item.
10. Quicksort the left sublist.
11. If there is a right sublist (L is still in the list) quicksort the right
sublist.
12. Stop.
I'm not sure how mergesort works, never having studied it, but I'm guessing it
splits the list into two parts, mergesorts the parts, then merges the parts
back into a single list. The merge part might require significant scratch
memory, unless you can find a good in-place merge algorithm.
Post a reply to this message
|
|
