.dsy:it. - [Bubblesort vs. Quicksort] Bellissimo!!

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Bubblesort vs. Quicksort] Bellissimo!! (http://www.dsy.it/forum/showthread.php?threadid=41595)

Posted by CowBoy on 15-02-2011 17:34:

[Bubblesort vs. Quicksort] Bellissimo!!

Che la sfida abbia inizio:

http://www.youtube.com/watch?v=vxENKlcs2Tw

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by xSharKMaNx on 15-02-2011 19:47:

http://www.geek.com/articles/geek-c...fects-20100819/

Buona visione

__________________
Perché, mentre il manganello può sostituire il dialogo, le parole non perderanno mai il loro potere; perché esse sono il mezzo per giungere al significato, e per coloro che vorranno ascoltare, all'affermazione della verità. E la verità è che c'è qualcosa di terribilmente marcio in questo paese. (V)

I popoli non dovrebbero aver paura dei propri governi, sono i governi che dovrebbero aver paura dei popoli. (T.J)

Posted by CowBoy on 15-02-2011 21:17:

Dubbio quicksort

Ho scritto l'algoritmo quicksort in VBA secondo le indicazioni trovate nella dispensa di Goldwurm, poiché svolgendo i calcoli a mano non riuscivo ad ordinare la sequenza in modo corretto.

L'array viene rappresentato dalla colonna A(A[1], A[2]... A[n]), contenente in celle consecutive una sequenza di numeri da ordinare. La pila viene rappresentata dalle colonne C e D.

Provo ad eseguire l'algoritmo e nella maggior parte delle volte la sequenza non è ordinata... sapete dirmi dove sto sbagliando?

HO RISOLTO!!! IL CODICE ADESSO FUNZIONA

code:
Function partition(ByVal p As Integer, ByVal q As Integer) As Integer
    Dim i As Integer
    Dim j As Integer

    i = p + 1
    j = q

    While (i <= j)
        While (Cells(j, 1) > Cells(p, 1))
            j = j - 1
        Wend

        While ((Cells(i, 1) <= Cells(p, 1)) And i <= j)
            i = i + 1
        Wend

        If i < j Then
            scambia i, j
            i = i + 1
            j = j - 1
        End If
        
    Wend

    scambia p, j
    partition = j

End Function

Function scambia(ByVal p As Integer, ByVal q As Integer)
    Dim t As Integer
    
    t = Cells(p, 1)
    Cells(p, 1) = Cells(q, 1)
    Cells(q, 1) = t

End Function

Function random(ByVal a As Integer, ByVal b As Integer) As Integer
    random = a + Rnd * (b - a)

End Function

Function quicksort(ByVal a As Integer, ByVal b As Integer)
    Dim p As Integer
    Dim q As Integer
    Dim k As Integer
    Dim l As Integer
    Dim x As Integer ' pila
    Dim s As Integer ' stop
    Dim i As Integer
    Dim j As Integer

    p = a
    q = b
    x = 0
    s = 0

    Do
        While p < q
            k = random(p, q)
            scambia p, k
            l = partition(p, q)

                If l - p < q - l Then
                    i = l + 1
                    j = q
                    q = l - 1
                Else
                    i = p
                    j = l - 1
                    p = l + 1
                End If

                x = x + 1
                Cells(x, 3) = i
                Cells(x, 4) = j
        Wend

        If x <> 0 Then
            p = Cells(x, 3)
            q = Cells(x, 4)
            x = x - 1
        Else
            s = 1
        End If
    Loop While (s = 0)
    
End Function



Sub exec()

    quicksort 1, Application.WorksheetFunction.Count(Range("A:A")) ' quicksort da 1 a n

End Sub

Potete provarlo sul foglio di lavoro nel post successivo...

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Posted by CowBoy on 15-02-2011 21:22:

Worksheet:

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

All times are GMT. The time now is 14:01.

Show all 4 posts from this thread on one page