QuickSort, hjææælp
Problemet er:Jeg har lavet et sorteringsprogram, som sorterer vha. Selectionsort. Det skulle gerne udvides til også at fungere med quicksort. Jeg har ikke nok rutine i at programmere quicksort selv, men har fundet et modul som kan benyttes og som virker.
Men i modulet er variablerne og listerne defineret på en måde jeg ikke kan overskue. Det er i hvertfald ikke lykkedes mig at få det til at fungere med Selectionsort's programmet. Håber nogen kan hjælpe med dette.
Her er først koden til selectionsort (udvælgelsessortering):
Option Explicit
Private Sub cmdGenerer_Click()
'genererer et array af heltal, blander tallene i
'arrayet og skriver til sidst arrayet til en random fil
'Hvis listen skal være næsten sorteret eller tilfældigt
'blandet, skrives tallene fra 1 til antal i arrayet
'i stigende orden. Skal listen være næsten omvendt sorteret
'skrives tallene fra 1 til antal i arrayet i omvendt
'rækkefølge. Herefter foretages der et antal ombytninger
'i arrayet: Ved næsten sorteret og næsten omvendt sorteret
'foretages der antal/10 ombytninger, ved helt tilfældigt
'foretages der antal*10 ombytninger.
Dim liste() As Integer
Dim AntalOmbytninger As Integer, i As Integer
Dim k As Integer, j As Integer
Dim temp As Integer
ReDim liste(1 To antal)
If optBlanding(0) Then 'næsten sorteret
AntalOmbytninger = antal \ 10
For i = 1 To antal
liste(i) = i
Next
ElseIf optBlanding(1) Then 'helt tilfældigt
AntalOmbytninger = antal * 10
For i = 1 To antal
liste(i) = i
Next
Else 'næsten omvendt
AntalOmbytninger = antal \ 10
For i = 1 To antal
liste(i) = antal - i + 1
Next
End If
Randomize
For i = 1 To AntalOmbytninger
k = Int(Rnd * antal) + 1
j = Int(Rnd * antal) + 1
'ombyt element nr. j og k i listen
temp = liste(k)
liste(k) = liste(j)
liste(j) = temp
Next
'skriv til fil:
Open talfil For Random As #1 Len = Len(i)
For i = 1 To antal
Put #1, i, liste(i)
Next
Close
Me.Hide
End Sub
Private Sub Form_Load()
'default-værdien for antal er 100
antal = 100
End Sub
Private Sub txtAntal_Change()
antal = Val(txtAntal)
End Sub
Option Explicit
Dim liste() As Integer
Dim AntalOmbytninger As Long
Dim AntalSammenligninger As Long
Private Sub cmdGenerer_Click()
Dim i As Integer, element As Integer
Kill talfil
List1.Clear
frmGenerer.Show vbModal
Open talfil For Random As #1 Len = Len(i)
For i = 1 To antal
Get #1, i, element
List1.AddItem element
Next
Close
lblAntal = antal
End Sub
Private Sub cmdUdvælg_Click()
Dim i As Integer, j As Integer
AntalOmbytninger = 0
AntalSammenligninger = 0
ReDim liste(1 To antal)
Open talfil For Random As #1 Len = Len(i)
For i = 1 To antal
Get #1, i, liste(i)
Next
Close
For i = 1 To antal - 1
For j = i + 1 To antal
If liste(i) > liste(j) Then ombyt i, j
AntalSammenligninger = AntalSammenligninger + 1
Next j
Next i
List1.Clear
For i = 1 To antal
List1.AddItem liste(i)
Next
lblSml = AntalSammenligninger
lblOmbyt = AntalOmbytninger
End Sub
Private Sub ombyt(e1 As Integer, e2 As Integer)
Dim temp As Integer
temp = liste(e1)
liste(e1) = liste(e2)
liste(e2) = temp
AntalOmbytninger = AntalOmbytninger + 1
End Sub
Option Explicit
Public antal As Integer
Public Const talfil = "talfil.srt"
OG KODEN TIL QUICKSORT (DEN SOM SKAL TILPASSES)
'Dette modul indeholder Quicksort algoritmen til at sorterer lister
'Algoritmen fungerer således: Der defineres et Pivotelement
'så listen partitioneres i to sub-lister: t(0 ... pivot -1)
'og t(pivot+1 ... n).
'Rekursivt patitioneres den venstre og højre partition.
'For at partitionere listen defineres to indeks: OP og NED.
'OP initialiseres til det første indeks i partitionen, og NED til
'til det sidste indeks i partitionen.
'Derudover initialiseres et Pivot-element til at være den første
'element i partitionen.
'OP bevæges til det første indeks, som indeholder det
'første element > pivot
'NED bevæges til det første indeks, som indeholder det første
'element < pivot. Elementerne ombyttes og proceduren gentages
'indtil up passerer down.
'
Public Sub QuickSort(ByRef t() As Variant, ByVal first As Double, ByVal last As Double)
'I denne procedure sorteres listen ved brug af QuickSort rekursivt
'This procedure recursivly sorts an array
'using QuickSort.
Dim pivot As Double
'Når første = sidste, kan listen ikke længere partitioneres.
If first < last Then
pivot = Partition(t, first, last) 'find pivotelementet ved at partitionering
QuickSort t, first, pivot - 1 'sorter den venstre partition
QuickSort t, pivot + 1, last 'sorter den højre partition
End If
End Sub
Public Function Partition(ByRef t() As Variant, ByVal first As Double, ByVal last As Double) As Double
'Denne funktion partitionerer listen t(første...sidste)til
't(første...pivot-1) hvis elementer alle er mindre end
'pivotelementet,og til t(pivot+1...last) hvis elementer
'alle er større end pivotelementet.
'
Dim up, down As Double
Dim pivot As Variant
pivot = t(first) 'pivotelementet sættes til at være det første værdi i partition
up = first 'intialiserer OP og NED
down = last
'Loop indtil OP passerer NED
Do While (up < down)
'forøg OP indtil det føste element,
'som er større end pivotelementet er nået
Do While (t(up) <= pivot) And (up < last)
up = up + 1
Loop
'Formindsk NED indtil det første element,
'som er mindre end pivotelementet er nået
Do While (t(down) > pivot)
down = down - 1
Loop
'Hvis OP ikke har passeret NED, skal elementerne ombyttes
If up < down Then Swap t(up), t(down)
Loop
'Ombyt pivotelementet med NED-elementet;
'pivot-elementet er nu i midten af partitionen
Swap t(first), t(down)
'Returner NED som indekset for det nye pivot-element
Partition = down
End Function
