HeapSort integer only?
Author Message
BruceKrautbauer

 Posted: Sat Mar 05 09:27:38 CST 2005 Top
 Visual Basic >> HeapSort integer only? I've been studying the sample at www.vbexplorer.com on different sort methods. also many other google pages on different sort algorithms. Every example of the heapsort I can find is on an integer array. Is it not possible to sort a string array with heapsort? What about count_sort? that also looks to be integer only? tia Mark Visual Studio257

erewhon

 Posted: Sat Mar 05 09:27:38 CST 2005 Top
 Visual Basic >> HeapSort integer only? >I've been studying the sample at >www.vbexplorer.com >on different sort methods. >also many other google pages on different sort algorithms. > >Every example of the heapsort I can find is on an integer array. >Is it not possible to sort a string array with heapsort? >What about count_sort? that also looks to be integer only? They can sort anything However, here is a Shell Sort for an array of strings ' ################################################### ' ' Sort A\$(1) to A\$(N) N is in A\$(0) ' Sub USArSort(A\$()) Dim Max%, L9%, L8%, Gap%, S\$ Max = Val(A\$(0)) Gap = Int(Max / 2) + 1 While Gap > 0 For L9 = 1 To Max - Gap For L8 = L9 To 1 Step -Gap If A\$(L8) > A\$(L8 + Gap) Then S\$ = A\$(L8) A\$(L8) = A\$(L8 + Gap): A\$(L8 + Gap) = S\$ 'SWAP A\$(L8), A\$(L8 + Gap) Else L8 = 0 End If Next Next Gap = Gap \ 2 Wend End Sub

MP

 Posted: Sat Mar 05 12:37:07 CST 2005 Top

MP

 Posted: Sat Mar 05 12:42:34 CST 2005 Top
 Visual Basic >> HeapSort integer only? > > The class property ToSort would be set to the array(byref) to sort and the > method Sort would do the sorting make that the class property Source would be set... :-)

erewhon

 Posted: Sat Mar 05 12:28:52 CST 2005 Top
 Visual Basic >> HeapSort integer only? >Thanks JFrench. >I do have a working shellsort method. And the beauty of that one is I can >actually grasp what it's doing. >I was looking at the heapsort and countsort since they're said to be so much >faster than the various others. >I confess after hours and hours of staring at the heap sort implementation I >still have no clue whats going on there - and that's probably my difficulty >in adapting the samples I've found in many google searches to put in my sort >class object. >Here's what I have that doesn't work but I don't understand why not. >I've attempted to take code shown in examples with hardwired arrays and >convert it into a class method. >The class property ToSort would be set to the array(byref) to sort and the >method Sort would do the sorting Not sure - I'm not that bothered with sorting algorithms since I settled on the Shell Sort in about 1984 Obviously if one knows the data then one uses insertion or maybe merging, but those are special cases. I can see one thing that is totally wrong : >'====================================================== >' Discussions of the Heap Sort revolve around nodes >' and sifting. The method defies simple explanation. >'====================================================== >'SteveMeyer >'http://trixar.com/~makai/sort1.htm >Private Sub Sort_Heap_meyer() > Dim j%, tmp% >Dim Last1% > > > 'Note: j = MAX - (MAX - MIN) \ 2 > j = Last1 - Last1 \ 2 \_______ that means that j is always zero > Do Until j >= Last1 > SiftUp_meyer Last1, j, 0 > j = j + 1 > Loop > > For j = 0 To Last1 - 1 > If m_ToSort(Last1) < m_ToSort(j) Then > tmp = m_ToSort(Last1) > m_ToSort(Last1) = m_ToSort(j) > m_ToSort(j) = tmp > > SiftUp_meyer Last1, Last1 - 1, j > End If > Next >End Sub

Larry

 Posted: Sat Mar 05 18:53:46 CST 2005 Top
 Visual Basic >> HeapSort integer only? > > >Every example of the heapsort I can find is on an integer array. > > >Is it not possible to sort a string array with heapsort? > > >What about count_sort? that also looks to be integer only? Yes it is possible to use strings in a heapsort, but a counting sort relies on the data being able to represent indices of an array. For a counting sort, if you want to sort numbers that were all in the range of 0 to 100, you would use an array of 101 elements. For data in the range of 0 to 1000, you would use an array of 1001 elements, etc. For every value in the data, you would increment the array element corresponding to that value. If you have a data value of 5, Sort(5) would be incremented, or if you have a value of 25, then Sort(25) would be incremented, and when you're all done, you can loop through the Sort array to list the data in ascending order by noting which elements have been icremented. It would complicate things to try to use a string to equate to the index values of the array, and in order for it to work, the strings would have to be sorted so that you can assign them to the right elements. Since the purpose of the routine is to sort the strings, Counting sort would not be useful to try to sort strings because you'd need to sort the strings to get that algorithm to work, so why move on after the you have the sorted list? > I was looking at the heapsort and countsort since they're said to be so much > faster than the various others. > I confess after hours and hours of staring at the heap sort implementation I > still have no clue whats going on there - and that's probably my difficulty > in adapting the samples I've found in many google searches to put in my sort > class object. Think of this heap as a binary tree. The simpliest version of that would be a parent with two kids. The next larger version would be a parent that has two kids, where each of the kids, have two kids, and so on... That is the structure you build, but typically you'll use an array to hold the values. With a parent at index 1, its kids are at index 2 and 3. The item at index 2 is also a parent, it has kids at index 4 and 5, 3's kids are at 6 and 7, and so on to build the structure, where the kids just use the next available items in the array. But, back to the binary tree, which is the heap, it will be in proper order when any one parent is larger in value than its two kids. If the kid is larger than its parent, then they need to be swapped. Typically, you'd begin a sort at the lowest leaves (where the root node is at the top of the structure) and sort the parent and kids out at the bottom of the heap to comform to the 'parent is larger than its kids' rule. Each set is a small 2 level heap. You'd then combine those initial heaps to form larger 3-level heaps by comparing parents of the two 2-level heaps. The larger one becomes the new parent and the other is compared to that new parent's kids (swapped with the larger kid). If you have to swap that old parent for the new parent's kid, remember that the old parent had its own set of kids, but since you are swapping the old parent for the largest kid of the new parent, that old parent's kids will still be smaller than the swaped value, keeping the Parent is Larger rule intact for the old parents heap. That is how you can combine heaps to form larger heaps. It may happen that you have a large difference between two compared parents where you end up pushing that old parent down the heap until it finds a kid it is larger than, (or it finds the end of the heap), but that is part of the algorithm to handle the comparing of two parents to form a new heap. When you have a value to add to the heap, you need to first increase the size of the array, then put that new value in the new element and compare it with its parent, moving it up the tree as needed. That is all find and dandy, but the tree may not be sorted in the array that holds the values. Example: ( Index/Value ) 1/Z 2/W 3/H 4/P 5/B 6/G 7/C That is a proper heap, but it is not yet sorted. If that were a string (in place of an array) it would be: ZWHPBGC Certainly not in any recognizable order..... To sort the values, take the root node (Z) out of the heap and grab that last element (C) and put it in its place. Shorten the array by one element and use the algorithm to push that value down to its proper position, making it a proper heap again. With the heap one element shorter than it was, you can then place that old root node in the array element that was freed up: 1/W 2/P 3/H 4/C 5/B 6/G XX As you see, the value C was removed from its former position and pushed down to index 4, restoring the heap to its proper structure. Now that XX element is not a part of the heap (but it is still a part of the array), that is where you store the old root node (Z) Again, with the heap in its proper form, the root node is the largest value and you repeat the process of pulling off that root, and taking the last element in the heap and adding it back in at the root, pushing down to wherever it needs to go, which restores the heap. You again shorten the heap by one element and put the pulled root in that newly freed position: 1/P 2/G 3/H 4/C 5/B XX XX The array (string in this case) would now look like: PGHCBWZ P is the new root and the next value to go would be at index 5 (B), and I'll leave it as an exercise for you to rebuild the heap, and determine how the array would appear.... Does that help? (Ref: "Visual Basic Algorithms" by Rod Stephens) LFS

MP

 Posted: Sat Mar 05 21:52:19 CST 2005 Top
 Visual Basic >> HeapSort integer only? > > > > > >Every example of the heapsort I can find is on an integer array. > > > >Is it not possible to sort a string array with heapsort? > > > >What about count_sort? that also looks to be integer only? > > > Yes it is possible to use strings in a heapsort, but a counting sort relies > on the data being able to represent indices of an array. For a counting sort, > if you want to sort numbers that were all in the range of 0 to 100, you would > use an array of 101 elements. For data in the range of 0 to 1000, you would use > an array of 1001 elements, etc. For every value in the data, you would increment > the array element corresponding to that value. If you have a data value of 5, > Sort(5) would be incremented, or if you have a value of 25, then Sort(25) > would be incremented, and when you're all done, you can loop through the > Sort array to list the data in ascending order by noting which elements have > been icremented. > > It would complicate things to try to use a string to equate to the index values > of the array, and in order for it to work, the strings would have to be sorted > so that you can assign them to the right elements. Since the purpose of the > routine is to sort the strings, Counting sort would not be useful to try to sort > strings because you'd need to sort the strings to get that algorithm to work, > so why move on after the you have the sorted list? > > > > I was looking at the heapsort and countsort since they're said to be so much > > faster than the various others. > > I confess after hours and hours of staring at the heap sort implementation I > > still have no clue whats going on there - and that's probably my difficulty > > in adapting the samples I've found in many google searches to put in my sort > > class object. > > Think of this heap as a binary tree. The simpliest version of that would be a > parent with two kids. The next larger version would be a parent that has two > kids, where each of the kids, have two kids, and so on... > > That is the structure you build, but typically you'll use an array to hold the values. > With a parent at index 1, its kids are at index 2 and 3. The item at index 2 is also > a parent, it has kids at index 4 and 5, 3's kids are at 6 and 7, and so on to build > the structure, where the kids just use the next available items in the array. > > But, back to the binary tree, which is the heap, it will be in proper order when any > one parent is larger in value than its two kids. If the kid is larger than its parent, > then they need to be swapped. > > Typically, you'd begin a sort at the lowest leaves (where the root node is at the > top of the structure) and sort the parent and kids out at the bottom of the heap > to comform to the 'parent is larger than its kids' rule. Each set is a small 2 level > heap. You'd then combine those initial heaps to form larger 3-level heaps by > comparing parents of the two 2-level heaps. The larger one becomes the new > parent and the other is compared to that new parent's kids (swapped with the > larger kid). > > If you have to swap that old parent for the new parent's kid, remember that the > old parent had its own set of kids, but since you are swapping the old parent > for the largest kid of the new parent, that old parent's kids will still be smaller than > the swaped value, keeping the Parent is Larger rule intact for the old parents heap. > > That is how you can combine heaps to form larger heaps. It may happen that > you have a large difference between two compared parents where you end up > pushing that old parent down the heap until it finds a kid it is larger than, (or > it finds the end of the heap), but that is part of the algorithm to handle the > comparing of two parents to form a new heap. > > When you have a value to add to the heap, you need to first increase the size > of the array, then put that new value in the new element and compare it with its > parent, moving it up the tree as needed. > > That is all find and dandy, but the tree may not be sorted in the array that holds > the values. Example: > > ( Index/Value ) > 1/Z > 2/W 3/H > 4/P 5/B 6/G 7/C > > That is a proper heap, but it is not yet sorted. If that were a string (in place of > an array) it would be: ZWHPBGC > > Certainly not in any recognizable order..... > > To sort the values, take the root node (Z) out of the heap and grab that last > element (C) and put it in its place. Shorten the array by one element and use > the algorithm to push that value down to its proper position, making it a proper > heap again. With the heap one element shorter than it was, you can then place > that old root node in the array element that was freed up: > > 1/W > 2/P 3/H > 4/C 5/B 6/G XX > > As you see, the value C was removed from its former position and pushed > down to index 4, restoring the heap to its proper structure. Now that XX > element is not a part of the heap (but it is still a part of the array), that is > where you store the old root node (Z) > > Again, with the heap in its proper form, the root node is the largest value > and you repeat the process of pulling off that root, and taking the last element > in the heap and adding it back in at the root, pushing down to wherever it > needs to go, which restores the heap. You again shorten the heap by one > element and put the pulled root in that newly freed position: > > 1/P > 2/G 3/H > 4/C 5/B XX XX > > The array (string in this case) would now look like: PGHCBWZ > P is the new root and the next value to go would be at index 5 (B), > and I'll leave it as an exercise for you to rebuild the heap, and determine > how the array would appear.... > > Does that help? > (Ref: "Visual Basic Algorithms" by Rod Stephens) > > LFS > wow that was awesome. I usually snip a bit to reply for the sake of bandwidth but that was just too beautiful to touch. Thank you very much. Mark your explanation was crystal clear, now to revisit the code and see if i can see it. thanks again

Larry

 Posted: Sun Mar 06 06:48:12 CST 2005 Top
 Visual Basic >> HeapSort integer only? > Thank you very much. You're welcome. > your explanation was crystal clear, now to revisit the code and see if i can > see it. thanks again Now that you have the structure in mind, it may help to point out (for those that didn't already know) that there is a direct relationship between the parent and child indices. If X is the index of a parent in a binary tree, its first child is always at index (2 * X) and the other child is at (2 * X) + 1. Likewise, if a child is at index Y then its parent is always at Int(Y/2). Knowing that bit of information allows for traversing up and down the tree, without having to keep pointers to all the kids. Have fun! LFS