Avatar billede morlar Nybegynder
14. februar 2002 - 20:14 Der er 1 kommentar og
1 løsning

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
Avatar billede hreiff Nybegynder
15. februar 2002 - 21:29 #1
Såvidt jeg kan se, skal du bare kalde proceduren sådan:

QuickSort liste, 1, antal

når du har genereret din liste af tilfældigetal.

Liste er listen med tal som skal sorteres,
1 er nummeret på den første i listen og
antal er nummeret på den sidste i listen (her 100)
Avatar billede hreiff Nybegynder
18. februar 2002 - 08:07 #2
Du kalder QuickSort i proceduren CmdUdvælg_Click


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
 
  QuickSort liste, 1, antal

  List1.Clear
  For i = 1 To antal
      List1.AddItem liste(i)
  Next
 
  lblSml = AntalSammenligninger
  lblOmbyt = AntalOmbytninger
End Sub

Hvis du skal bruge Antal sammenligninger og ombytninger må du ændre lidt på QuickSort koden (markeret med '***********):

Public Sub QuickSort(ByRef t() As Variant, ByVal first As Double, ByVal last As Double)

    Dim pivot As Double
   
    AntalSammenligninger = AntalSammenligninger + 1  '*****
    If first < last Then
        pivot = Partition(t, first, last)
        QuickSort t, first, pivot - 1
        QuickSort t, pivot + 1, last
    End If
End Sub

Public Function Partition(ByRef t() As Variant, ByVal first As Double, ByVal last As Double) As Double
       
    Dim up, down As Double
    Dim pivot As Variant
   
    pivot = t(first)
    up = first
    down = last
   
    Do While (up < down)
        Do While (t(up) <= pivot) And (up < last)
            up = up + 1
            AntalSammenligninger = AntalSammenligninger + 1  '*****
        Loop
        Do While (t(down) > pivot)
            down = down - 1
            AntalSammenligninger = AntalSammenligninger + 1  '******
        Loop
        If up < down Then
          Swap t(up), t(down)
          AntalOmbytninger = AntalOmbytninger + 1  '**************
        End If    '**********
    Loop
   
    Swap t(first), t(down)
    AntalOmbytninger = AntalOmbytninger + 1  '****************

    Partition = down
End Function
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester