Strona: [  << <   1   > >>  ]  z  1     
Autor Temat: quick sort
monia



Typ: neutral
Postów: 26
Zarejestrowany: Apr 2003
quick sort

heheh znów mam wielguśny problem..

czy ktoś tu kapuje sortowanie quicksortem ??
w sumie to wiem, jak ta maszyna działa, ale cuś mi kiepsko wychodzi przetworzenie tego co mam w główce na kod, w taki sposób, żeby pecek się nie pogubił..
wszelkie próby zakończone fiaskiem...


_____________________________________________
nic co ludzkie, nie jest mi obce

12-05-2003 22:23
Pokaż profil monia  Wyślij email do monia        4894458
Ushy




Typ: neutral
Postów: 87
Zarejestrowany: Mar 2003

z tego co zdazylem sie polapac.. to quicsort dziala na takiej zasadzie 2 petli.. ktore jednoczesnie od lewej i od prawej sprawdzaja poszczegolne wartosci w tablicy.

Jak juz ci pisalem znalazlem przyklad wykonany w delphi... wszystko ladnie.. sa dwie petelki.. ale pojawias ie cos takiego.. taka funkcja:

'quick'
ktorej to odpowiednika w vb nie ma... a ona jest najwazniejsza

sam jestem ciekaw jak by to mozna zrobic... poszperam troche na innych forach.


_____________________________________________
www.KURDE.pl

13-05-2003 01:15
Pokaż profil Ushy  Wyślij email do Ushy   Odwiedź stronę Ushy       3299912
monia



Typ: neutral
Postów: 26
Zarejestrowany: Apr 2003

Ushasty Ushasty widzę, że się starasz

wyszperałam w mojej mądrej książce strasznie długachny kodzik... tam piszą, że ponoć to działa bezproblemowo, tyle że trza by dopisać cuś żeby wyświetlało efekty sortu (jak domniemywam to pewnie im chodzi o dopisek np. pod commandem)...
całość może nie wygląda aż tak paskudnie...
generalnie używają tylko dziwnie zdefiniowanych zmiennych... z wersji napisanych w VB, ta wydaje mi się w miarę przystępna... tyle że nie dla mnie... przyznam szczerze, że patrząc na to w zasadzie nic nie widzę, mimo że ideę działania sortu  rozumiem..

przykładowo nie wiem jak zastosować to, powiedzmy do tablicy 10-cio elementowej, gdzie elementy są losowo wybranymi integerami... w tej kwestii jestem pogrążona w głębokiej niewiedzy..

pozwolę sobie przesłać Ci to na priva, może Tobie uda się coś z tego wydusić... a może przyda Ci się to do tej przeróbki z Delphi..


_____________________________________________
nic co ludzkie, nie jest mi obce

13-05-2003 02:15
Pokaż profil monia  Wyślij email do monia        4894458
Ushy




Typ: neutral
Postów: 87
Zarejestrowany: Mar 2003

hm ciekawy algorytm... ktos sie nameczyl i napisal procedurke... ktora w delphi juz jest zdefiniowana ... (jakktos chce oblukac do )

zaraz pokombinuje jak to teorie upraktycznic

w tym samplu delphi (jak znajde to podrzuce) wygladalo to tak.. ze byla pierwsza petla zwykla For i=cos to cos step 1
quick() 'u nas tutaj odwolamy sie do porcedurki
gor i=cos to cos step -1

tak mniej wiecej.. hmm... sprobuje przeanalizowac ten kod.. ale przyznam sie ze mnie strasza te petle


_____________________________________________
www.KURDE.pl

13-05-2003 12:32
Pokaż profil Ushy  Wyślij email do Ushy   Odwiedź stronę Ushy       3299912
herszt_mielony



Typ: neutral
Postów: 17
Zarejestrowany: Apr 2003
Herszt powraca ;)

Musisz mieć Command1 i Text1

A oto funkcja z komentarzami:

Private Sub QuickSort(anArray As Variant, StartEl As Long, StopEl As Long)
Dim workStart As Long, workStop As Long
Dim x As Variant, y As Variant, i As Long
    If VarType(anArray) < vbArray Then Exit Sub
    workStart = StartEl
    workStop = StopEl
    ' pobierz element położony w połowie między
    ' przekazanymi indeksami StartEl
    ' i StopEl. Nadaj zmiennej X jego wartość
    x = anArray((StartEl + StopEl) / 2)
    ' teraz X przechowuje element położony
    ' w połowie zakresu indeksów tablicy
    ' Przy pierwszym wywołaniu procedury ten zakres to
    ' StartEl = LBoundCarray), StopEl -UBoundCarray).
    ' W kolejnych rekurencyjnych wywołaniach poniżej.
    ' wykorzystywane są zmienione wartości tych parametrów.
    ' Teraz sprawdzimy zakres zmiennych workStart
    ' i workStop. a potem przypiszemy dwóm zmiennym
    ' tymczasowym odpowiadające im dane potrzebne do późniejszych
    ' porównań.
   
    ' Tutaj sprawdzamy, czy workStart (dolny indeks)
    ' nie przekracza workStop (maksymalnie StapEl)
    While (workStart <= workStop)
        ' dopóki workStart jest mniejsze niż workStop,
        ' porównujemy wartość bieżącego elementu tablicy
        ' i ustalonej powyżej wartości X. Ponadto musimy
        ' sprawdzać, czy workStart nadaj jest
        ' mniejsze od wartości granicznej StopEl.
        While (anArray(workStart) < x And workStart < StopEl)
            workStart = workStart + 1
        Wend
        ' kontunuujemy dla wartości tablicy na pozycji workStop,
        ' również sprawdzając, czy workStop nadal jest większe
        ' od wartości granicznej StartEl.
        While (x < anArray(workStop) And workStop > StartEl)
            workStop = workStop - 1
        Wend
        ' Na podstawie porównania ostatecznych pozycji
        ' workStart i workStop ustalamy, które elementy
        ' zamienić miejscami
        If (workStart <= workStop) Then
            'a. Nadaj zmiennej tymczasowej Y wartość
            ' anArray(workStart)
            'b. Zamień elementy anArray(workStop) i anArray(workStart)
            'c. Nadaj anArray(workStop) wartość zapisaną w
            ' zmiennej tymczasowej Y .
            y = anArray(workStart)
            anArray(workStart) = anArray(workStop)
            anArray(workStop) = y
            'zmodyfikuj zakres indeksów
            workStart = workStart + 1
            workStop = workStop - 1
        End If
    Wend
    ' jeśli początkowa wartość StartEl jest nadal mniejsza
    ' od workStop, wywołujemy tę samą procedurę
    ' dla punktu początkowego StartEl i punktu końcowego
    ' workStop
    If (StartEl < workStop) Then QuickSort anArray, StartEl, workStop
    ' a jeśli workStart jest nadal mniejsza od StapEl,
    ' wywołujemy naszą procedurę dla punktu początkowego WorkStart
    ' i punktu końcowego StapEl
    If (workStart < StopEl) Then QuickSort anArray, workStart, StopEl
End Sub

I bez:

Private Sub QuickSort(anArray As Variant, StartEl As Long, StopEl As Long)
Dim workStart As Long, workStop As Long
Dim x As Variant, y As Variant, i As Long
    If VarType(anArray) < vbArray Then Exit Sub
    workStart = StartEl
    workStop = StopEl
    x = anArray((StartEl + StopEl) / 2)
    While (workStart <= workStop)
        While (anArray(workStart) < x And workStart < StopEl)
            workStart = workStart + 1
        Wend

        While (x < anArray(workStop) And workStop > StartEl)
            workStop = workStop - 1
        Wend
        If (workStart <= workStop) Then
            y = anArray(workStart)
            anArray(workStart) = anArray(workStop)
            anArray(workStop) = y
            workStart = workStart + 1
            workStop = workStop - 1
        End If
    Wend
    If (StartEl < workStop) Then QuickSort anArray, StartEl, workStop
    If (workStart < StopEl) Then QuickSort anArray, workStart, StopEl
End Sub

Przykład użycia:

Private Sub Command1_Click()
Dim ARR(9) As Integer
Dim i As Integer
    ARR(0) = 5
    ARR(1) = 9
    ARR(2) = 3
    ARR(3) = 0
    ARR(4) = 4
    ARR(5) = 2
    ARR(6) = 1
    ARR(7) = 7
    ARR(8) = 8
    ARR(9) = 6
    Call QuickSort(ARR(), 0, 9)
    Text1.Text = ""
    For i = 0 To 9
        Text1.Text = Text1.Text & ARR(i) & " "
    Next i
End Sub

Nio, koniec wykładu, ewakuacja na przerwę!

13-05-2003 20:21
Pokaż profil herszt_mielony  Wyślij email do herszt_mielony   
monia



Typ: neutral
Postów: 26
Zarejestrowany: Apr 2003

oj Herszciu
ja tu nie lada szpeca w Tobie widzę.. skąd żeś ty to wytrzasnął ?
no to mi teraz dałeś do myślenia.. minie troche czasu nim to przetrawię... ale historia zna przypadki na pewno działa ...


_____________________________________________
nic co ludzkie, nie jest mi obce

13-05-2003 23:28
Pokaż profil monia  Wyślij email do monia        4894458
Ushy




Typ: neutral
Postów: 87
Zarejestrowany: Mar 2003

szacunek... zrob jakiegos sampla z tym i posylaj redakcyji


_____________________________________________
www.KURDE.pl

14-05-2003 13:17
Pokaż profil Ushy  Wyślij email do Ushy   Odwiedź stronę Ushy       3299912
herszt_mielony



Typ: neutral
Postów: 17
Zarejestrowany: Apr 2003

Trzeba se skopiować kod, dodać button i textbox o nazwach Command1 i Text1 i uruchomić. Sampel gotowy

14-05-2003 18:46
Pokaż profil herszt_mielony  Wyślij email do herszt_mielony   
Wszystkich odpowiedzi: 7 :: Maxymalnie na stronę: 20
Strona: [  << <   1   > >>  ]  z  1