HeapSort integer only?  
Author Message
BruceKrautbauer





PostPosted: 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 Studio341  
 
 
erewhon





PostPosted: 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





PostPosted: Sat Mar 05 12:37:07 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
>

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

code to test the class

Sub testsort()
Dim aTest(4) As String
aTest(0) = "Garbanzo"
aTest(1) = "apples"
aTest(2) = "cantelope"
aTest(3) = "Banana"
aTest(4) = "Fruit"

Dim aTest2(4) As Integer
aTest2(0) = 5
aTest2(1) = 3
aTest2(2) = 12
aTest2(3) = 1
aTest2(4) = 4

Dim lIdx As Long
Debug.Print "Array starts: "
For lIdx = 0 To 4
Debug.Print aTest(lIdx)
Next

'for now class is named SortHeap
Dim adcSort As SortHeap
Set adcSort = New SortHeap
'set the array to sort
'here a string array
adcSort.Source = aTest
'sort it
adcSort.Sort
'print results
Debug.Print "Array Ends: "
For lIdx = 0 To 4
Debug.Print aTest(lIdx)
Next

'now try with integer array
Debug.Print "Array starts: "
For lIdx = 0 To 4
Debug.Print aTest2(lIdx)
Next

adcSort.Source = aTest2
adcSort.Sort

Debug.Print "Array Ends: "
For lIdx = 0 To 4
Debug.Print aTest2(lIdx)
Next

Set adcSort = Nothing
End Sub

'code in the class
Option Explicit
Private m_iAscend As Integer
Private m_bascending As Boolean
'private member variable to hold array to be sorted
Private m_ToSort As Variant
Private lower As Long
Private upper As Long
Public Property Let Source(ByRef vData As Variant)

m_ToSort = vData
lower = LBound(m_ToSort)
upper = UBound(m_ToSort)

End Property

Public Property Get Ascending() As Boolean
Ascending = m_bascending
End Property
Public Property Let Ascending(vData As Boolean)
m_bascending = vData
If m_bascending Then
m_iAscend = 1
Else
m_iAscend = -1
End If

End Property

Public Sub Sort()
'Sort_Heap
Debug.Print "Try meyer sort"
Sort_Heap_meyer
End Sub

'======================================================
' 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

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

Private Sub SiftUp_meyer(first%, ByVal midl%, last%)
Dim k%, k1%, m1%, tmp%

k = (midl - first) * 2 + first
Do While k >= last
If k > last Then
k1 = k + 1
If m_ToSort(k) < m_ToSort(k1) Then
k = k - 1
End If
End If

k1 = k + 1
m1 = midl + 1

If m_ToSort(k1) < m_ToSort(m1) Then
tmp = m_ToSort(k1)
m_ToSort(k1) = m_ToSort(m1)
m_ToSort(m1) = tmp
Else
Exit Do
End If
midl = k
k = (midl - first) * 2 + first
Loop
End Sub


'and heres the results
Array starts:
Garbanzo
apples
cantelope
Banana
Fruit
Try meyer sort
Array Ends:
Garbanzo
apples
cantelope
Banana
Fruit
Array starts:
5
3
12
1
4
Try meyer sort
Array Ends:
5
3
12
1
4



 
 
MP





PostPosted: 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...
<obviously>
:-)


 
 
erewhon





PostPosted: Sat Mar 05 12:28:52 CST 2005 Top

Visual Basic >> HeapSort integer only?

<snip>

>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 :

<snip>

>'======================================================
>' 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





PostPosted: 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





PostPosted: 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





PostPosted: 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