[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

Binary quick sorting

Posted on 2002-06-12
7
Medium Priority
?
320 Views
Last Modified: 2010-05-02
I am looking for the full algorithm for binary quick sorting in VB.
The algorithm should sort a array of strings in binary order.
Help appreciated...


Martin Schmalz
0
Comment
Question by:cyber_bulldog
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
7 Comments
 
LVL 2

Expert Comment

by:vbDoc
ID: 7073887
0
 
LVL 5

Expert Comment

by:rpai
ID: 7073916
0
 

Expert Comment

by:HobbitHouse
ID: 7074159
[vbcode]
'
' test QSORT on a vector of strings
'
Private Sub cmdSort3_Click()
    Dim thelist(10) As String
    Dim ix As Integer
    For ix = 0 To 9
        thelist(ix) = Chr(70 + ((ix + 5) Mod 9)) + "aB"
    Next ix
    Debug.Print "-----------"
    For ix = 0 To 9
        Debug.Print thelist(ix)
    Next ix
    Call QuickSort(thelist, 0, 9)
    Debug.Print ""
    For ix = 0 To 9
        Debug.Print thelist(ix)
    Next ix
End Sub
'
' QSORT modified to handle public MyType indexes as elements
'
' The SortList passed in (and recursed) is an index on a vector
' of MyType structures.  The COMPARISON is done on the actual
' internal MyType element which is the sort key (S2 in this case)
' thus when the QSORT is finished, the SortList is a vector of
' indexes which can then be used to get at the MyType vector
' in sorted order.
'
Public Sub QuickSort2(SortList As Variant, ByVal First As Integer, ByVal Last As Integer)
    Dim Low As Integer, High As Integer         'Use Integer for lists up to 32,767 entries.
    Dim temp1 As Variant, TestElement As Variant 'Variant can handle any type of list.
    Low = First
    High = Last
    TestElement = lst(SortList((First + Last) / 2)).S2  'Select an element from the middle.
    Do
        Do While lst(SortList(Low)).S2 < TestElement    'Find lowest element that is >= TestElement.
            Low = Low + 1
        Loop
        Do While lst(SortList(High)).S2 > TestElement   'Find highest element that is <= TestElement.
            High = High - 1
        Loop
        If (Low <= High) Then                   'If not done,
            temp1 = SortList(Low)                ' Swap the elements.
            SortList(Low) = SortList(High)
            SortList(High) = temp1
            Low = Low + 1
            High = High - 1
        End If
    Loop While (Low <= High)
    If (First < High) Then QuickSort2 SortList, First, High
    If (Low < Last) Then QuickSort2 SortList, Low, Last
End Sub
[/vbcode]
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 5

Accepted Solution

by:
Julian_K earned 300 total points
ID: 7075610
Hi.
You mean creating a binary tree, ect?
0
 
LVL 5

Expert Comment

by:Julian_K
ID: 7075653
Hi again.
By the way, If you need just a FAST algorythm, and NOT ONLY a binary tree, I have one method handy.

It makes approximately:
Log(2)X comparitions
to find the place of an element in an array of X elements.
Say It's an array of 1024 elements, it will do 10 comparitions; or 20 comparitions for an array of 2^20 elements.

So, to sort ALL elements in an array, it takes:
Sum(1 to x) of Log2(I) comparitions
to sort X elements (where I is from 1 to X)

0
 
LVL 5

Expert Comment

by:Julian_K
ID: 7211081
Hello again. I had forgoten this question, sorry...
Here is the method I often use to sort arrays.
I have moved the comparition to a procedure, so you could change it according to your needs - you may be comparing more than just one value.
"Command1_Click" - just to test it.
I'm sure this method could be improved, but I don't have time to think of it now.
I hope this will help You.

Private Sub Command1_Click()
    SortArray (Array(1, 9, 17, 5, 2, 7, 4, 3, 6, 8, 10, 15, 16, 14, 12, 13, 18, 11))
End Sub

Private Sub SortArray(ByRef vntArr As Variant)
       
        Dim lngLLimit As Long     'lower array limit
        Dim lngTotalItems As Long 'upper array limit
       
        Dim lngULimit As Long   'upper limit of sorted items
       
        Dim lngCurrent As Long  'current item being sorted
        Dim lngChecked As Long  'item being checked with the current
       
        Dim lngLSeekLimit As Long   'last smaller detected item
        Dim lngUSeekLimit As Long   'last bigger detected item
       
        Dim I As Long, vntItem As Variant   'used to move items
       
        Dim lngCounter As Long  'just to count comparition operations, you can remove it.
       
   
    lngTotalItems = UBound(vntArr)  'get upper bound of the array
    lngLLimit = LBound(vntArr)      'get lower bound of the array
    lngULimit = lngLLimit + 1       'sorted items in the array (=2)
   
    'sort first and second items in the array
    If IsBigger(vntArr(lngLLimit), vntArr(lngULimit)) Then
        vntItem = vntArr(lngLLimit)
        vntArr(lngLLimit) = vntArr(lngULimit)
        vntArr(lngULimit) = vntItem
    End If
   
   
    'repeat until the last item is sorted
    Do Until lngULimit = lngTotalItems
   
        lngCurrent = lngULimit + 1  'this item will be sorted
        lngLSeekLimit = lngLLimit   'this is the smaller known item
        lngUSeekLimit = lngULimit   'this is the biggest known item
       
        lngCounter = 0  'reset comparitions counter
       
        'find place where then new item will be moved to
        Do
            'get middle item of the sorted items list
            lngChecked = (lngUSeekLimit - lngLSeekLimit) \ 2 + lngLSeekLimit
           
            lngCounter = lngCounter + 1
           
            'if the new item is bigger than the middle element, change boundaries
            If IsBigger(vntArr(lngCurrent), vntArr(lngChecked)) Then
                lngLSeekLimit = lngChecked + 1
            Else
                lngUSeekLimit = lngChecked - 1
            End If
        Loop Until lngLSeekLimit > lngUSeekLimit
       
        'move the new item to its proper place
        vntItem = vntArr(lngCurrent)
        For I = lngULimit To lngLSeekLimit Step -1
            vntArr(I + 1) = vntArr(I)
        Next I
        vntArr(lngLSeekLimit) = vntItem
       
        'display operation on the screen. This code is for demo only - remove it.
        For I = lngLLimit To lngTotalItems
            Debug.Print vntArr(I) & "  ";
            If I = lngCurrent Then Debug.Print "/ ";
        Next I
        Debug.Print " -> [" & lngCounter & " comparitions]"
       
        'increase the sorted items counter
        lngULimit = lngULimit + 1
    Loop
   
End Sub

Private Function IsBigger(ByVal vntFirst As Variant, ByVal vntSecond As Variant) As Boolean
    IsBigger = (vntFirst > vntSecond)
End Function
0
 
LVL 5

Expert Comment

by:Julian_K
ID: 7211097
You can speed it up, if you use second array to store results into - this way it won't be neccesary to move the elements to allocate space for each new sorted item.
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Enums (shorthand for ‘enumerations’) are not often used by programmers but they can be quite valuable when they are.  What are they? An Enum is just a type of variable like a string or an Integer, but in this case one that you create that contains…
This article describes how to use a set of graphical playing cards to create a Draw Poker game in Excel or VB6.
As developers, we are not limited to the functions provided by the VBA language. In addition, we can call the functions that are part of the Windows operating system. These functions are part of the Windows API (Application Programming Interface). U…
Get people started with the process of using Access VBA to control Outlook using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Microsoft Outlook. Using automation, an Access applic…
Suggested Courses

650 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question