Array Sorting 6

[GDX]

Lets say i have an array:

a(6)

And the array contains the following information:

A(1) = 3
A(2) = 1
A(3) = 6
A(4) = 8
A(5) = 2
A(6) = 9

How do i sort these numbers from lowest to highest? I can't seem to figure this one out, Also i cant use any built in VB Functions. Gordon R. Durgha
gd@vslink.net

http://www.vslink.net

http://www.brainbench.com/transcript.jsp?pid=1217371

 

[swilliams]

Try This:

Dim i As Long
Dim j As Long
Dim k As Long
For i = 0 To UBound(a)
If i = 0 Then
ReDim b(0)
b(i) = a(i)
Else
ReDim Preserve b(i)
For j = 0 To UBound(b)
If b(j) >= a(i) Then
For k = UBound(b) - 1 To j Step -1
b(k + 1) = b(k)
Next k
b(j) = a(i)
Exit For
End If
Next j
End If
Next i

a is the array that is already set, b is a new array that is created from a but sorted in ascending order.

Simon

 

[culshaja]

You could try the bubble sort algoritms or swap algorithms.
The bubble sort algorithm uses multiple passes along the array and if the first number is greater than the second then swap them around.
The following code is a rather bad example:

dim intA as integer
dim intCounter as integer
dim blnSwapped as boolean

blnSwapped = True

while blnSwapped
  blnSwapped = False  
  for intCounter = LBound(A) to (UBound(A) - 1)
    if A(intCounter) > A(intCounter + 1) then
      intA = A(intCounter)
      A(intCounter) = A(intCounter + 1)
      A(intCounter + 1) = intA
      blnSwapped = True
    end if
  next intCounter
wend

It has rather a high complexity (n squared! i think) and so is inefficientfor large arrays but it works.

James James Culshaw
jculshaw@active-data-solutions.co.uk

http://www.active-data-solutions.co.uk

http://www.brainbench.com/transcript.jsp?pid=193305

 

[TomSark]

Yes, if you have more than 50 or 100 items, I wouldn't use these simplistic sorting algorithms (like a bubble sort).

Quick sort is the fastest sort that I know of...

Tom

 

[swilliams]

What is "Quick sort"???

Simon

 

[culshaja]

dim lngMidPoint as Long
dim lngLBound as ling
dim lngUBound as long
dim intA as integer
dim intB as integer

lngLBound = LBound(A)
lngUBound = UBound(A)

lngMidPoint = A(lngLBound + lngUBound)\2

intA = A(lngMidPoint)

do while (lngLBound <= lngUBound)

  do while A(lngLBound) < intA 
    lngLBound = lngLBound + 1
    if lngUBound = lngLBound then
      exit do
    end if
  loop

  do while intA < A(lngUBound)
    lngUBound = lngUBound - 1
    if lngUBound = lngLBound then
      exit do
    end if
  loop

  if (lngUbound <= lngUBound) then
    intB = A(lngLBound)
    A(lngLBound) = A(lngUBound)
    lngUBound = intB
    lngLBound = lngLBound + 1
    lngUBound = lngUBound - 1
  end if

loop

This needs to be put in a sub which is then called recusively. You will need to move the determination of Lower and Upper Bound to outside the call and pass them in.

James James Culshaw
jculshaw@active-data-solutions.co.uk

http://www.active-data-solutions.co.uk

http://www.brainbench.com/transcript.jsp?pid=193305

 

[Snaggs]

There are several flavors of QuickSort. The one that James gave is non recursive (which is a rare find). Most of the ones I have seen are recursive. Tom is right... QuickSort is much faster than the BubbleSort. I've also found that the MergeSort is just as fast if not faster than QuickSort, especially if you have a large amount of data to sort. QuickSort on the one hand is great for large sets. However for smaller amounts of data it's not as efficient as others, but still it's faster than most.

That last sentence almost made me sound like a politician! First I was for it, then I was against it. YIKES - What's happening to me!
Snaggs
tribesaddict@swbell.net

 

[rvBasic]

A good overview of sorting algorithms with their applicability can be found at:

http://www.vb2themax.com/HtmlDoc.asp?Table=Articles&ID=10

 

[GDX]

I am trying to create something simple so everytime i click the command button it will sort, this is what I have so far but where it has the "---" this is where i am having a little problem. The error i get is "Expected sub, function or property"

Dim numz(6) As Integer
numz(1) = 4
numz(2) = 3
numz(3) = 7
numz(4) = 6
numz(5) = 8
numz(6) = 9

For i = 1 To 6
If numz(i) > numz(i) + 1 Then
numz (i) + 1 = numz(i) ---
Else
End If
Next i Gordon R. Durgha
gd@vslink.net

http://www.vslink.net

http://www.brainbench.com/transcript.jsp?pid=1217371

 

[Snaggs]

The problem is a classic one when first learning to program. I commend you for your effort on this one. Before I tell you what the error is, lets look at what the line is doing:

numz (i) + 1 = numz(i)

first of all the space that shows up between the numz and the (i) on the left side should raise a red flag in your mind that something is wrong with the syntax. Notice how the (i) is next to the numz on the right hand side of the = sign? This is what the left side should look like too.

Now for examining the line. The left side is saying, "Take the value in numz(i) and add 1 to it. After all it does say numz(i) + 1. I think the true intention was to add 1 to the index, not to the value in the array. So what it really should read is numz(i + 1). This doesn't change the value in the array, it just determines what element is selected. Now for the error. Well, by now you should see it. The left hand side of the = sign is really an equation. The equation must be put on the right side of the equal sign. The variable on the left is what gets assigned the value. So if we say:

numz(i+1) = numz(i)

This can be properly evaluated.

If you're intention is to sort this list, then we can't just over write the upper element. The comparison statement is correct. When we swap two values, we need a temporary holding location, like another variable. We really need to do something like this:

temp = numz(i)
numz(i) = numz(i+1)
numz(i+1) = temp

Now we have successfully swapped the value without changing them. Now lets look at the loop. The loop is hard coded for 1 thru 6. This brings up two issues. First, if we dim the array for 6 elements, then the last element we can access is 6. So when we hit the statement "numz(i) = numz(i+1)" we will get a "Subscript out of range" error. Why? Well 6+1 is 7, and that's outside the boundary of the array. So what we need to do is say:

For i = 1 to 6 - 1

Now this might look funny, but there is a good reason to code it this way as you'll see later. At first glance you might ask, why not just put 5 in there, it's the same thing. However when I look at it, it tells me that there are really 6 elements, but we're only going to the second to last element. It's a symantec thing.

Secondly, if we only go through the loop one time, then the values may not be fully sorted. Some of the numbers might be reordered, however the list may still be out of order. So here's what we have so far:

The way the sort works is it bubbles the higher values up from the beginning of the list and bubbles the lower values down from the end of the list. Higher numbers move --> and lower numbers move <--. So the first time through the list the highest number will be last in the list. So there is no reason to check this again since we are sure that this number is in the correct spot. Now we need to go through the list again and get the next highest number to the end of the list, well, next to the highest value in the list. So the pattern is that every time we go through the list, the next highest value will find its spot in the list. Since we know they are sorted, it's a wasted effort to check them. So we want to keep moving the end of the list to the left. This is how we do that. We use two counters. i and j, not good names, but we're not talking about naming conventions. <grin>.

Dim numz(6) As Integer, i As Integer, j As Integer
Dim temp As Integer

numz(1) = 4
numz(2) = 3
numz(3) = 7
numz(4) = 6
numz(5) = 8
numz(6) = 9

For i = 6 To 1 Step -1
For j = 1 To i - 1
If numz(j) > numz(j + 1) Then
temp = numz(j + 1)
numz(j + 1) = numz(j)
numz(j) = temp
End If
Next j
Next i

Notice the For i = 6 to 1 Step -1. We are starting at the end of the loop first. This i variable determines where the j loop will stop. Every time through the loop i will decrement. Why? Because the bigger numbers get bubbled to the end of the list and we know they are in the correct location. At this point, the list will be properly sorted. However, there are some finishing touches that I would put on it.

1. I would not hardcode the value of the array boundary. Let the program figure this out for out. It makes for self-maintaining code. This is a big plus. I'd do this with the UBound and LBound functions.

2. I would set a flag to let me know if I went all the way through the list and nothing got swapped, then I know the list is sorted. For example if there were 100 numbers and only 2 of them were out of order, say 99, 98 then I would have several more passes through the loop that were worthless checks.

3. I would create a function and pass the array to the function. This is for reusability. Another big plus.

4. I would use the zeroth element of the array also or define &quot;Option Base 1&quot; at the top of the module. I chose to use the 0 element.

The final code would look like this:

Private Sub Form_Load()
Dim numz(6) As Integer

numz(0) = 5
numz(1) = 4
numz(2) = 3
numz(3) = 7
numz(4) = 6
numz(5) = 8
numz(6) = 9

BubbleSort numz()
End Sub

Private Sub BubbleSort(Numbers() As Integer)
Dim bSwap As Boolean
Dim i As Integer, j As Integer, temp As Integer

For i = UBound(Numbers) To LBound(Numbers) Step -1
bSwap = False

For j = LBound(Numbers) To i - 1
If Numbers(j) > Numbers(j + 1) Then
temp = Numbers(j + 1)
Numbers(j + 1) = Numbers(j)
Numbers(j) = temp
bSwap = True
End If
Next j

'Comment the following line out and see how many more iterations it takes.
If Not bSwap Then Exit For
Next i
End Sub

Well, that's the lesson for sorting with BubbleSort. I hope this sheds some light on the algorithm for you. Snaggs
tribesaddict@swbell.net

 

[GDX]

Wow thanks a lot for that extensive tutorial it really helps!!! Gordon R. Durgha
gd@vslink.net

http://www.vslink.net

http://www.brainbench.com/transcript.jsp?pid=1217371

 

[jeba]

If you want to be lazy and don't care about effeciency you could do the this:

put a listbox control on your form and set the &quot;visible&quot; property to false. Set the &quot;sorted&quot; property to true.

Then

dim itemstosort(100) as string ' assume this array is filled with items

dim ix as integer

if your base option is set to 0 then

ix = 0
Do until ix > 99
list1.additem itemstosort(ix)
ix = ix + 1
Loop
ix = 0
Do until ix > list1.ListCount
itemstosort(ix) = list1.List(ix)
ix = ix + 1
Loop

because the sort property is true VB will sort the items in the list box for you. All you have to do is load the listbox and unload it.

If the items are of integer type you would have to cstr() and Format() before adding to the listbox and cint() when reloading the itemstosort
You would need to format so that the items in the list were the same length with leading zeros.