Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Asembler - quicksort

qba1986 24 Maj 2008 14:14 1500 1
  • #1 24 Maj 2008 14:14
    qba1986
    Poziom 9  

    Piszę algorytm szybkiego sortowania w asemblerze a dokładniej jest to dll w asmie w projekcie z pisanym w c++ i mam pewnien problem - algortym źle sortuje dane. Oto mój algorytm w asmie:

    Code:

    QuickSort PROC tablica:dword, ilosc:sdword
    start:
                  push EAX
       push EBX
       push ECX
       push EDX
       push ESI
       push EDI
       push EBP
       push ESP
       mov EAX, 0
       push EAX;  lewy na stos
       mov EAX, ilosc
       dec EAX
       push EAX; prawy na stos   
       mov EAX, 0
       push EAX; piwot na stos (piwot = 0)
    poczatek:   
       mov EBX, 2
       pop EDX; EDX = piwot
       mov EDX, 0; zerowanie rejestru EDX
       pop EAX; zaladowanie prawego do EAX   
       pop ECX; zaladowanie lewego do ECX
       push ECX; lewy na stos
       push EAX; prawy na stos
       add EAX, ECX; prawy + lewy
       div EBX; EAX = (prawy+lewy)/2
       mov ESI, EAX; przypisanie wartosci do zmiennej i
       mov EDX, tablica
       mov EBX, [EDX+EAX*4]
       pop EAX; pobranie prawego EAX = prawy
       mov ECX, [EDX+EAX*4]; ECX = tablica[prawy]
       mov [EDX+ESI*4], ECX; tablica[i] = tablica[prawy]   
       pop ECX; ECX = lewy   
       mov EDI, ECX; j = lewy   
       mov ESI, ECX; i = lewy
       push ECX; odlozenie lewego na stos
       push EAX; odlozenie prawego na stos
       push EBX; odlozenie piwota na stos
       mov EDX, tablica
    petla1:   
       pop EBX; EBX = piwot
       pop EAX; EAX = prawy
       push EAX; prawy na stos
       push EBX; piwot na stos
       cmp ESI, EAX; porownanie i z prawym
       jae dalej2
       mov ECX, [EDX+ESI*4]; ECX = tablica[i]
       cmp ECX, EBX; porownanie tablica[i] z piwotem
       mov ilosc, EBX
       mov ilosc, ECX
       jge dalej1
       mov EBX, [EDX+EDI*4]; EBX = tablica[j]
       mov [EDX+ESI*4], EBX
       mov [EDX+EDI*4], ECX
        inc EDI
    dalej1:   
       inc ESI
       jmp petla1
    dalej2:
       mov EBX, [EDX+EDI*4]; EBX = tablica[j]
       pop EAX; EAX = piwot
       pop ECX; ECX = prawy




       push EAX; piwot na stos
       mov [EDX+ECX*4], EBX; tablica[prawy] = tablica[j]
       pop EAX; EAX = piwot
       mov [EDX+EDI*4], EAX; tablica[j] = piwot   
       mov EDX, EDI; EDX = j
       dec EDX
       pop EBX; EBX = lewy
       push EBX; lewy na stos
       push ECX; prawy na stos
       push EAX; piwot na stos
       cmp EBX, EDX
       mov EDX, tablica; EDX = tablica
       jb dalej3
       pop EAX; EAX = piwot
       pop ECX; ECX =  prawy
       mov EBX, EDI; EBX = j
       inc EBX
       cmp EBX, ECX
       push ECX; prawy na stos
       push EAX; piwot na stos
       jb dalej4
       jmp koniec
    dalej3:
       pop EAX; EAX = piwot
       pop ECX; ECX = prawy
       mov ECX, EDI; prawy = j
       dec ECX; prawy = j-1
       push ECX; prawy na stos
       push EAX; piwot na stos
       jmp poczatek
    dalej4:
       pop EAX; EAX = piwot
       pop ECX; ECX = prawy
       pop EBX; EBX = lewy
       mov EBX, EDI; lewy = j
       inc EBX; lewy = j+1
       push EBX; lewy na stos
       push ECX; prawy na stos
       push EAX; piwot na stos
       jmp poczatek      
    koniec:
       pop EAX
       pop ECX
       pop EBX
       pop ESP
       pop EBP
       pop EDI
       pop ESI
       pop EDX
       pop ECX
       pop EBX
       pop EAX      
       ret
    QuickSort ENDP   
    END DllEntry

    parametr tablica to adres tablicy podawanej jako parametr przy wywołaniu funkcji w C++, zaś ilość to liczba elementów tej tablicy.
    Napisałem sobie tez ten alogorytm w C++ zeby zobaczyć jak będzie on sortował dane. Wiem na czym polega bład w algorytmie w asemblerze ale nie potrafie tego rozwiązać. Tzn algortym w asemblerze sortuje dokładnie tak jak ten algorytm napisany poniżej w C++:
    Code:

    void szybkie(int lewy, int prawy)
    {
       int i,j, piwot;
       i = (lewy+prawy)/2;
       piwot = c[i];
       c[i] = c[prawy];
       j = lewy;
       i = lewy;
       while (i<prawy)
       {
          if(c[i] < piwot)
          {
             pom = c[i];
             c[i] = c[j];
             c[j] = pom;
             j++;
          }
          i++;
       }
       c[prawy] = c[j];
       c[j] = piwot;
       if (lewy<j-1)
          szybkie(lewy, j-1);
       else
       {
          if(j+1<prawy)
             szybkie(j+1, prawy);
       }
    }
     

    Natomiast poprawny algorytm powinien wyglądać tak jak poniżej tzn bez tego jednego "elsa":
    Code:

    void szybkie(int lewy, int prawy)
    {
       int i,j, piwot;
       i = (lewy+prawy)/2;
       piwot = c[i];
       c[i] = c[prawy];
       j = lewy;
       i = lewy;
       while (i<prawy)
       {
          if(c[i] < piwot)
          {
             pom = c[i];
             c[i] = c[j];
             c[j] = pom;
             j++;
          }
          i++;
       }
       c[prawy] = c[j];
                c[j] = piwot;
       if (lewy<j-1)
          szybkie(lewy, j-1);
       if(j+1<prawy)
          szybkie(j+1, prawy);
    }
     

    Jeśli ktoś z Was wie jak przerobić algorytm w asmie żeby poprawnie sortował dane tak jak ten alogorytm w C++ powyżej to prosiłbym bardzo o pomoc. Pozdrawiam.

    0 1
  • #2 26 Maj 2008 07:52
    Dżyszla
    Poziom 42  

    Nie prościej byłoby przeprowadzić asemblerację kodu i ewentualnie w nim wprowadzić poprawki? Nie wiem, czy przypadkiem skoku nie masz źle wykonanego - rekurencyjnie chyba źle wychodzi z funkcji (nie sprawdza drugiej rekurencji). Ale to tak tylko spogladając - najlepiej to po prostu zdebugować.

    0