[VB] Array Alfabetisch Sorteren - Optimalisatie

[WhiteDog]

Ik heb in mijn software een soort adresboekje zitten. Aangezien niet iedereen mooi alfabetisch z'n naampjes ingeeft () sorteer ik de array dus voor het opslaan. De reden waarom ik een array gebruik en geen database ofzo is hier verder niet relevant

De lijst word gesorteerd op PhoneBook(i).Name, waarbij lege waarden NIET meegerekend worden en dus naar achteren verplaatst worden... Het werkt allemaal vrij goed, alleen in bepaalde situaties loopt er wat mis... bv als er helemaal vooraan en achteraan items staan komen ze niet altijd goed. Daarom sort ik de lijst voorlopig 2x.

Graag had ik jullie reacties en optimalisaties van me code Het laatste stukje code zorgt voor het verplaatsen van de lege items naar achteren...

Alvast bedankt!

PHP:

Public Type PhoneNumberType
    Name As String
    Number As String
    Comment As String
    Groups As String
End Type
Public PhoneBook() As PhoneNumberType

Public Sub Sort(ByRef SortArray() As PhoneNumberType, ByVal UBArray As Integer)
    Dim TempSwap As PhoneNumberType
    Dim i As Integer
    Dim j As Integer
    Dim Counter As Integer
    For i = 0 To UBArray
        If UCase(SortArray(i).Name) = "" Then Counter = Counter + 1
        For j = 0 To UBArray
            If UCase(SortArray(j).Name) > UCase(SortArray(i).Name) Then
                TempSwap = SortArray(i)
                SortArray(i) = SortArray(j)
                SortArray(j) = TempSwap
            End If
        Next
    Next
    j = 0
    For i = Counter To UBArray
        TempSwap = SortArray(j)
        SortArray(j) = SortArray(i)
        SortArray(i) = TempSwap
        j = j + 1
     Next
End Sub

[johnwoo]

Niet echt het meest efficiente algoritme, maar zelfs dit algoritme kan nog wat getweakt worden
- In beide loopjes begin je bij 0. Waarom? Het binnenste loopje kan je bij i + 1 laten beginnen; de elementen daarvoor zijn al vergeleken met het i'de element van de buitenste loop in de vorige iteraties van die loop. Die buitenste hoeft dan dus ook niet tot UBArray, maar tot UBArray - 1
- Gebruik StrComp ipv de > operator; die is vele malen sneller (iirc )
- Je kan een sorteerslag ook geheel voorkomen, door nieuwe elementen direct op de juiste plaats in te voegen. Hierdoor kun je wel nogal vervelende verplaatsingen krijgen in het geheugen als het een beetje en lange lijst is (of de elementen groot zijn). Dit is dan weer op te lossen door een linked list te gebruiken ipv een array, zodat de elementen op willekeurige plaatsen in het geheugen mogen staan.

edit:
drZymo: niet in VB

[drZymo]

Extra tip :
In iedere programmeer taal zit vaak al een geimplementeerde versie van een van de snellere zoek algoritme, namelijk Quicksort. Als ik jou was zou ik die eens op zoeken.

[CyberSnooP]

Het is al min-of-meer gezegd maar: Zoek eens naar sorteer-algoritmes op internet. Er zijn zoveel mensen die er over hebben nagedacht en die waarschijnlijk tot oplossingen zijn gekomen die je zelf niet ff bedenkt. Ik verwacht niet dat de duidelijkste uitleg vergezeld gaat met Visual Basic code, maar het kan heeeel leerzaam zijn om te pogen zelf pseudo-code om te zetten naar een VB-implementatie. Google er op los dus!

[.oisyn]

sorteren is in dit geval vrij nutteloos, je zou natuurlijk ook bij het invoeren de elementen gelijk op de goede plek kunnen zetten (tip: gebruik een gelinkte lijst)

[Soultaker]

.oisyn schreef op 14 oktober 2002 @ 00:52:
(tip: gebruik een gelinkte lijst)

Misschien gaat het voor deze toepassing wat ver, maar een heap is natuurlijk nog beter. Dan kun je ze in O(log(N)) invoeren en er gesorteerd uittrekken.

[Denhomer]

http://www.experts-exchan...ual_Basic/Q_20237867.html

Dan ook nog een stukje uit de msdn library:

code:

Function QuickSortArray(varArray As Variant, _ 
                        Optional lngFirst As Long = -1, _ 
                        Optional lngLast As Long = -1) As Variant 
    ' QuickSort algorithm used to sort the items 
    ' in the varArray array. 
     
    Dim lngLow      As Long 
    Dim lngHigh     As Long 
    Dim lngMiddle   As Long 
    Dim varTempVal  As Variant 
    Dim varTestVal  As Variant 
     
    If lngFirst = -1 Then lngFirst = LBound(varArray) 
    If lngLast = -1 Then lngLast = UBound(varArray) 
         
    If lngFirst < lngLast Then 
        lngMiddle = (lngFirst + lngLast) / 2 
        varTestVal = varArray(lngMiddle) 
        lngLow = lngFirst 
        lngHigh = lngLast 
        Do 
            Do While varArray(lngLow) < varTestVal 
                lngLow = lngLow + 1 
            Loop 
            Do While varArray(lngHigh) > varTestVal 
                lngHigh = lngHigh - 1 
            Loop 
            If (lngLow <= lngHigh) Then 
                varTempVal = varArray(lngLow) 
                varArray(lngLow) = varArray(lngHigh) 
                varArray(lngHigh) = varTempVal 
                lngLow = lngLow + 1 
                lngHigh = lngHigh - 1 
            End If 
        Loop While (lngLow <= lngHigh) 
        If lngFirst < lngHigh Then QuickSortArray varArray, lngFirst, lngHigh 
        If lngLow < lngLast Then QuickSortArray varArray, lngLow, lngLast 
    End If 
End Function

komt dus van http://msdn.microsoft.com...ode/modPublicDefs_bas.asp

Beide zijn quicksorts

[Verwijderd]

Zoek eens in google naar hoe je met CopyMemory en AddressOff arrays kunt manipuleren. Dat is de snelste manier om met een array om te gaan.

Kijk bijv eens naar http://www.freevbcode.com/ShowCode.Asp?ID=2536