Quicksort af Arrays ... Bevis at du er en "ekspert"

Jamen hvad er det da du vil? -Har du din egen kode du vil ha' sorteret eller hvad er det du vil?

//>Rune

Jeg vil gerne have udvidet funktionen som du finder på hjemmeside ... så man kan sortere på 2 koloner ... altså skal der indsættes en ekstra kolone ...

hehe...der giver jeg op :o)

Det eksempel som der er på sitet er for uoverskuelig... Jeg vil gerne hjælpe dig, men så skal du oxo forklare hvad det er du vil, og evt. vise mig noget kode jeg kan arbejde med...

//>Rune

Hm.. er ikke 100% sikker på, jeg er med på, hvad du mener, men hvis det er en quicksort til sortering af et 2d array, kan du finde en på 4guys:

http://www.4guysfromrolla.com/webtech/012799-3.shtml

Den funktion jeg henviser til er en udvidet udgave af den funktion på 4guysfromrolla.

Okay det drejer som om følgende kode:

''' Regular Array Sort

Sub QuickSort(vec,loBound,hiBound,SortField,SortDir)
  '==--------------------------------------------------------==
  '== Sort a multi dimensional array on SortField            ==
  '==                                                        ==
  '== This procedure is adapted from the algorithm given in: ==
  '==    ~ Data Abstractions & Structures using C++ by ~    ==
  '==    ~ Mark Headington and David Riley, pg. 586    ~    ==
  '== Quicksort is the fastest array sorting routine for    ==
  '== unordered arrays.  Its big O is n log n                ==
  '==                                                        ==
  '== Parameters:                                            ==
  '== vec      - array to be sorted                        ==
  '== SortField - The field to sort on (1st dimension value) ==
  '== loBound and hiBound are simply the upper and lower    ==
  '==  bounds of the array's "row" dimension. It's probably ==
  '==  easiest to use the LBound and UBound functions to    ==
  '==  set these.                                          ==
  '== SortDir  - ASC, ascending; DESC, Descending          ==
  '==--------------------------------------------------------==
  if not (hiBound - loBound = 0) then
      Dim pivot(),loSwap,hiSwap,temp,counter
      Redim pivot (Ubound(vec,2))
      SortDir = UCase(SortDir)

      '== Two items to sort
      if hiBound - loBound = 1 then
        if (SortDir = "ASC") then
            if FormatCompare(vec(loBound,SortField),vec(hiBound,SortField)) > FormatCompare(vec(hiBound,SortField),vec(loBound,SortField)) then Call SwapRows(vec,hiBound,loBound)
        else
            if FormatCompare(vec(loBound,SortField),vec(hiBound,SortField)) < FormatCompare(vec(hiBound,SortField),vec(loBound,SortField)) then Call SwapRows(vec,hiBound,loBound)
        end if
      End If

      '== Three or more items to sort
      For counter = 0 to Ubound(vec,2)
        pivot(counter) = vec(int((loBound + hiBound) / 2),counter)
        vec(int((loBound + hiBound) / 2),counter) = vec(loBound,counter)
        vec(loBound,counter) = pivot(counter)
      Next

      loSwap = loBound + 1
      hiSwap = hiBound

      do
        '== Find the right loSwap
        if (SortDir = "ASC") then
            while loSwap < hiSwap and FormatCompare(vec(loSwap,SortField),pivot(SortField)) <= FormatCompare(pivot(SortField),vec(loSwap,SortField))
              loSwap = loSwap + 1
            wend
        else
            while loSwap < hiSwap and FormatCompare(vec(loSwap,SortField),pivot(SortField)) >= FormatCompare(pivot(SortField),vec(loSwap,SortField))
              loSwap = loSwap + 1
            wend
        end if
        '== Find the right hiSwap
        if (SortDir = "ASC") then
            while FormatCompare(vec(hiSwap,SortField),pivot(SortField)) > FormatCompare(pivot(SortField),vec(hiSwap,SortField))
              hiSwap = hiSwap - 1
            wend
        else
            while FormatCompare(vec(hiSwap,SortField),pivot(SortField)) < FormatCompare(pivot(SortField),vec(hiSwap,SortField))
              hiSwap = hiSwap - 1
            wend
        end if
        '== Swap values if loSwap is less then hiSwap
        if loSwap < hiSwap then Call SwapRows(vec,loSwap,hiSwap)
      loop while loSwap < hiSwap

      For counter = 0 to Ubound(vec,2)
        vec(loBound,counter) = vec(hiSwap,counter)
        vec(hiSwap,counter) = pivot(counter)
      Next

      '== Recursively call function .. the beauty of Quicksort
        '== 2 or more items in first section
        if loBound < (hiSwap - 1) then Call QuickSort(vec,loBound,hiSwap-1,SortField,SortDir)
        '== 2 or more items in second section
        if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound,SortField,SortDir)
  end if
End Sub  'QuickSort

Sub SwapRows(ary,row1,row2)
  '==------------------------------------------==
  '== This proc swaps two rows of an array    ==
  '==------------------------------------------==

  Dim x,tempvar
  For x = 0 to Ubound(ary,2)
    tempvar = ary(row1,x)
    ary(row1,x) = ary(row2,x)
    ary(row2,x) = tempvar
  Next
End Sub  'SwapRows

function FormatCompare(sOne,sTwo)
  '==------------------------------------------==
  '==  Checks sOne & sTwo, returns sOne as a  ==
  '==  Numeric if both pass isNumeric, if not  ==
  '==  returns sOne as a string.              ==
  '==------------------------------------------==

    if (isNumeric(Trim(sOne)) AND isNumeric(Trim(sTwo))) then
        FormatCompare = CDbl(Trim(sOne))
    else
        FormatCompare = Trim(sOne)
    end if
end function

Sub PrintArray(vec,loRow,hiRow,markCol)
  '==------------------------------------------==
  '== Print out an array  Highlight the column ==
  '==  whose number matches param markCol      ==
  '==------------------------------------------==

  Dim ColNmbr,RowNmbr
  Response.Write "<table border=""1"" cellspacing=""0"">"
  For RowNmbr = loRow to hiRow
    Response.Write "<tr>"
    For ColNmbr = 0 to (Ubound(vec,2) - 1)
      If ColNmbr = markCol then
        Response.Write "<td bgcolor=""FFFFCC"">"
      Else
        Response.Write "<td>"
      End If
      Response.Write vec(RowNmbr,ColNmbr) & "</td>"
    Next
    Response.Write "</tr>"
  Next
  Response.Write "</table>"
End Sub  'PrintArray

Forestil dig at du smider nogle data ind i det 2d array. Herefter kalder du funktionen og vælger at sortere på en af kolonerne. Denne kolone indeholder nogle steder de samme data. Derfor ville det være godt hvis man kunne kalde funktionen med en estra parametre nemlig SortField2 ...

Er I med nu ?

Nok det allerstørste problem med at programmere er at få kunden til at fortælle hvad pokker det egentlig er han ønsker

1) Hvad er det der skal sorteres?
  Definer klart og tydeligt de klumper der skal flyttes rundt på.

2) Hvilken sorteringsregel skal der benyttes?
  Når jeg står med 2 af dine klumper i hånden hvordan bestemmer jeg så hvilken der er størst?
  Hvilke af de data der er i klumpen skal jeg bruge til at beslutte det?
  Hvilken regel skal jeg bruge for at afgøre at "989" er større end "11"? er det fordi talle 999 er større and tallet 10, eller forsi bogstavet '9' står efter bogstavet '1' i alfabetet, eller fordi strengen "999" indeholder flere bogstaver end strengen "10".
  Det er vigtigt at vide for om et øjeblik skal jeg måske sammenligne "99" med "100".
  med hver af de 3 regler bliver "989", "11", "99", "100" sorteret forskelligt:
  tallet:    "11", "99", "100", "989"
  bogstaver:  "100", "11", "989", "99"
  strengen:  "11", "99", "989", "100"

Det er først når du har het helt og aldeles klart du begynder på at tænke på hvilken metode du vil bruge til at sorter dine data.

i spm http://www.eksperten.dk/spm/212425 siger du:
"Jeg er ved at lave en webmail (i ASP) hvor jeg viser en liste over meddelser i indbakken (via jMail). For at kunne sortere denne liste efter afsender, emne, størrelse og data/tid fik jeg den idé at man kunne stoppe dataene ind i et array og derefter trække dem ud sorteret igen ..."
og det fortæller faktisk noget om hvilke 'klumper' der skal sorteres. Det er emails hvor hver email består af
  afsender, emne, størrelse, dato, indhold
hver email kan så være et lille array med 5 elementer.

Få medions eller hvilken ASP-er der nu vil til at hjælpe dig med at lave et ASP array (eller måske en struktur) der kan indeholde alle de data der er i een e-mail og skal sorteres. NB. kun een email her i første runde. det er formatet på en enkelt klump vi skal have slået fast.

Det næste bliver så at beslutte hvordan der skal sorteres hvilke meget klare og faste regler der skal bruges for at beslutte at een email-klump er større end en anden.

og først til allersidst, når det er gjort, er det umagen værd at kikke på sorteringsprogrammet, finde ud af hvilke klumper det program sorterer og hvordan dine klumper kan sættes ind istedetfor. Hvilke regler det program bruger og hvordan dine regler kan sættes ind istedetfor.

mvh JakobA

Det der skal sorteres er datene i en webmail. Her er et eksmepel på datene i en mail.

Afsender: Torben Melander
Emne: Webmail
Dato: 22-6-02 15:39
Størrelse: 2 KB

ud over disse skal der også være en skjult kolone som indeholder et tal, men denne skal der ikke kunne sorteres på. I praktisk kan den bare laves som en kolone i arrayet hvor man bare ikke laver nogle links til at sortere på denne.

Altså er indholdet altid en streng.

Ud fra det andet spm. du nævner har jeg fundet ud af at en Quicksort metode vil være en god løsning med hensyn til performance ...

Til dette har jeg fundet ovenstående kode ... som sådan set virker fint, bortset fra at man kunne ønske sig en mulighed for at vælge en ekstra kolone at sortere på...

Hvis vi tager et eksempel (Afsender, Emne, Dato, Størrelse):

Torben Melander, TEST1, 22-6-02 15:00, 2 KB
Torben Melander, TEST2, 22-6-02 15:15, 2 KB
Torben Melander, TEST3, 22-6-02 15:30, 2 KB

Hvis man sortere på Afsender som i dette tilfølde er den samme vil man fordi Quicksort deler arrayet op i flere dele få et resultat som dette:

Torben Melander, TEST3, 22-6-02 15:30, 2 KB
Torben Melander, TEST1, 22-6-02 15:00, 2 KB
Torben Melander, TEST2, 22-6-02 15:15, 2 KB

hvilket egentlig er rigtigt nok eftersom der sorteres på Afsender ... men det kunne da være fedt hvis man kunne angive at man ville sortere på kolonen Emne også ...

Nu kan det godt være at Quicksort metoden er god med hensyn til performance... men er det bedre at bruge en anden metode med hensyn til sortering på flere koloner af gangen ?

Håber I forstår hvad jeg mener ...

Lukker eftersom ingen kan finde ud af det ...

Måske denne her kan hjælpe dig, den sortere godt nok på 3 columns:

'** Sort any 2 dimensional array by the first 3 colums. Array looking like MyArr(Columns, Rows) **'
Function DoubleSorter(byRef arrArray)
  Dim ColmunLenght, row,i , j, StartingValues(), NewStartingValues(), swap_pos

  '** Column-Lenght of array **'
  ColmunLenght = UBound(arrArray, 1)
  ReDim StartingValues(ColmunLenght): ReDim NewStartingValues(ColmunLenght)
 
  '** Start outer loop **'
  For row = 0 To UBound(arrArray, 2)
 
    'Take a snapshot of the first element in the array because if there is a
    'smaller value elsewhere in the array we'll need to do a swap.
    For i = 0 To ColmunLenght
      StartingValues(i) = arrArray(i, row)
    Next
   
    ' Default the Starting values to the First Record
    For i = 0 To ColmunLenght
      NewStartingValues(i) = arrArray(i, row)
    Next
   
    swap_pos = row

    '** Start inner loop **'
    For j = row + 1 to UBound(arrArray, 2)
      swap = false
      If arrArray(0, j) < NewStartingValues(0) Then
        swap = true
      ElseIf arrArray(0, j) = NewStartingValues(0) Then
        If arrArray(1, j) < NewStartingValues(1) Then
          swap = true
        ElseIf arrArray(1, j) = NewStartingValues(1) Then
          If arrArray(2, j) < NewStartingValues(2) Then
            swap = true
          End If
        End If
      End If
      If swap then
        'This is now the lowest number - remember it's position.
        swap_pos = j
        For i = 0 To ColmunLenght
          NewStartingValues(i) = arrArray(i, j)
        Next
      End If
    Next
       
    If swap_pos <> row Then
      'If we get here then we are about to do a swap within the array.
     
      '** Set new starting values **'
      For i = 0 To ColmunLenght
        arrArray(i, swap_pos) =  StartingValues(i)
      Next
     
      '** Set swapped values **'
      For i = 0 To ColmunLenght
        arrArray(i, row) =  NewStartingValues(i)
      Next
         
    End If   
  Next
End Function

'** Print array **'
Function printArray(myArr)
  Response.Write "<table border=1>"
  For i = 0 To UBound(myArr,2)
    Response.Write "<tr>"
    For j = 0 To UBound(myArr,1)
      Response.Write "<td>"
      Response.Write myArr(j,i)
      Response.Write "</td>"
    Next
    Response.Write "</tr>"
  Next
  Response.Write "</table>"
End Function

Randomize

Dim theArray(2,9)
'** Create array **'
For i = 0 To UBound(theArray,2)
  For j = 0 To UBound(theArray,1)
    theArray(j,i) = Int((3 * rnd) + 1)
  Next
Next

Call printArray(theArray)
Call DoubleSorter(theArray)
Call printArray(theArray)