elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  ASM (Moderador: Eternal Idol)
| | | |-+  [ASM]Algoritmo de Ordenacion Quicksort
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [ASM]Algoritmo de Ordenacion Quicksort  (Leído 12,755 veces)
ny0x


Desconectado Desconectado

Mensajes: 336


Ver Perfil
[ASM]Algoritmo de Ordenacion Quicksort
« en: 24 Junio 2009, 04:04 am »

Bueno aqui les dejo una traduccion a ensamblador del algoritmo de QuickSort me costo algo de trabajo y estuve un buen depurando pero por fin salio.
Lo malo es que solo funciona con numeros de 32 bits positivos pero se puede arreglar para que funcionen con bytes y words (ahora lo de negativos no se intente cambiar jl y jg por jb y ja pero me los pone como mayores que cualquier positivo)

Si de casualidad alguien no entiende el codigo que me diga y le pongo comentarios   ;)

Código
  1. format pe console
  2. include '\fasm\include\win32ax.inc'
  3. entry start
  4. .data
  5. vector          dd      32,9,11,5,99,3,1,2,5,12,100,4365
  6. formato         db      '%i %i %i %i %i %i %i %i %i %i %i %i',13,10,0
  7. .code
  8. start:
  9.        call Dump
  10.        push 11
  11.        push 0
  12.        push vector
  13.        call quicksort
  14.        call Dump
  15.  
  16. ret
  17.  
  18. quicksort:
  19.         push ebp
  20.         mov ebp,esp
  21.         push esi
  22.         push ebx
  23.         push ecx
  24.         push edx
  25.         mov ebx,dword[ebp + 12]
  26.         mov ecx,dword[ebp + 16]
  27.         cdq
  28.         mov eax, ebx
  29.         add eax, ecx
  30.         push ecx
  31.         mov ecx,2
  32.         div ecx
  33.         pop ecx
  34.         xchg edx,eax
  35.         mov esi, [ebp + 8]
  36.         mov edx,dword[esi + edx * 4]
  37.         qs@L1:
  38.                qs@L1@L1:
  39.                        cmp dword[esi + ebx * 4],edx
  40.                        jge qs@L1@L1@out
  41.                        inc ebx
  42.                        jmp qs@L1@L1
  43.                qs@L1@L1@out:
  44.                qs@L1@L2:
  45.                        cmp dword[esi + ecx * 4],edx
  46.                        jle qs@L1@L2@out
  47.                        dec ecx
  48.                        jmp qs@L1@L2
  49.                qs@L1@L2@out:
  50.                qs@L1@IF1:
  51.                        cmp ebx, ecx
  52.                        jg qs@L1@IF1@out
  53.                        mov eax, dword[esi + ebx * 4]
  54.                        xchg eax, dword[esi + ecx * 4]
  55.                        mov dword[esi + ebx * 4], eax
  56.                        inc ebx
  57.                        dec ecx
  58.                qs@L1@IF1@out:
  59.                cmp ebx,ecx
  60.                jle qs@L1
  61.         qs@L1@out:
  62.         qs@IF1:
  63.                cmp dword[ebp + 12],ecx
  64.                jge qs@IF1@out
  65.                push ecx
  66.                push dword[ebp + 12]
  67.                push esi
  68.                call quicksort
  69.         qs@IF1@out:
  70.         qs@IF2:
  71.                cmp ebx, dword[ebp + 16]
  72.                jge qs@IF2@out
  73.                push dword[ebp + 16]
  74.                push ebx
  75.                push esi
  76.                call quicksort
  77.         qs@IF2@out:
  78.         pop edx
  79.         pop ecx
  80.         pop ebx
  81.         pop esi
  82.         pop ebp
  83. retn 12
  84.  
  85. Dump:
  86.        pushad
  87.        mov edi,vector
  88.        push dword[edi + 11 * 4]
  89.        push dword[edi + 10 *4 ]
  90.        push dword[edi + 9 * 4]
  91.        push dword[edi + 8 * 4]
  92.        push dword[edi + 7 * 4]
  93.        push dword[edi + 6 * 4]
  94.        push dword[edi + 5 * 4]
  95.        push dword[edi + 4 * 4]
  96.        push dword[edi + 3 * 4]
  97.        push dword[edi + 2 * 4]
  98.        push dword[edi + 1 * 4]
  99.        push dword[edi]
  100.        push formato
  101.        call [printf]
  102.        add esp,52
  103.        popad
  104. ret
  105. section '.idata' import data readable
  106. library msvc,'msvcrt.dll'
  107. import msvc,printf,'printf'
  108.  

los parametros se pasan por la pila
y son asi
quicksort(int *vector, int izq, int der)


En línea

h0oke


Desconectado Desconectado

Mensajes: 2.059


Coder ~


Ver Perfil WWW
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #1 en: 24 Junio 2009, 04:05 am »

Exelente trabajo x0ʎu se nota que estas progresando bastante.
Ya tendré mi tiempito para dedicarme a asm.
S2!


En línea

Arkangel_0x7C5


Desconectado Desconectado

Mensajes: 361



Ver Perfil
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #2 en: 24 Junio 2009, 04:16 am »

gran trabajo de traducción amigo.

saludos Arkangel
En línea

YST


Desconectado Desconectado

Mensajes: 965


I'm you


Ver Perfil WWW
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #3 en: 24 Junio 2009, 04:31 am »

Muy buen code , para que sea compatible con byte y word se podria usar cbw y cwd :P solo es una idea para alguien que lo quiera usar.

Por si alguien no conoce de que trata el algoritmo
http://es.wikipedia.org/wiki/Quicksort
En línea



Yo le enseñe a Kayser a usar objetos en ASM
ny0x


Desconectado Desconectado

Mensajes: 336


Ver Perfil
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #4 en: 24 Junio 2009, 04:34 am »

gracias  :-[
tarde mucho depurando pero por lo menos quedo mas o menos decente  :)

P.D si no quieren que les cause un error cuando tienen un numero negativo cambien los saltos  jl y jg por jb y ja, lo unico malo es que los negativos los ordenara como mayores   :(

Yst si se que se puede y tambien se puede adaptar para que ordene qwords  :xD
En línea

YST


Desconectado Desconectado

Mensajes: 965


I'm you


Ver Perfil WWW
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #5 en: 24 Junio 2009, 06:09 am »

Por que el gracias con cara triste ???

Lo que me gustaria ver es el algoritmo RC4 en ASM , talves lo haga yo :P
En línea



Yo le enseñe a Kayser a usar objetos en ASM
Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #6 en: 25 Junio 2009, 00:04 am »

Muy buen trabajo este, felicitaciones!!!  ;-) ;-)
En línea





Mi blog:
http://amerikanocls.blogspot.com
Yurix

Desconectado Desconectado

Mensajes: 72


Paz para la guerra y guerra por la paz


Ver Perfil
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #7 en: 25 Junio 2009, 18:26 pm »

Bravo  :o , según he leído en el foro este algoritmo es el mas rápido , felicidades poco a poco vamos ampliando el repertorio y compartiendo , felicidades , te invito a que lo publiques en la wikipedia , si lo deseas lo puedo hacer yo.

Saludos
En línea



http://kapetres.wordpress.com/ < Mi blog sobre ASM

Parece que alguien no quiere que la info sea liebre >

Alguien lo movio a ese lugar.
YST


Desconectado Desconectado

Mensajes: 965


I'm you


Ver Perfil WWW
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #8 en: 26 Junio 2009, 10:47 am »

Basado en el Ordenamiento por Selección

hice un codigo para ordenar bytes :P

Este metodo tambien sirve para hacer un orden alfabetico ya que los caracteres ascii estan en orden alfabetico :P
Código
  1. include 'win32ax.inc'
  2.  
  3. .data
  4. cc db '774422990',0
  5. .code
  6. start:
  7. invoke lstrlen,cc
  8. stdcall Ordenar,cc,eax
  9. invoke MessageBox,0,cc,0,0
  10. invoke ExitProcess,0
  11.  
  12. proc Ordenar,cNumer,cCantidad
  13. pushad
  14. pushf
  15. mov edi,[cCantidad]
  16. mov ebx,[cNumer]
  17. dec ebx
  18. inc edi
  19. .bucle:
  20. dec edi
  21. inc ebx
  22. stdcall Menor,ebx,edi
  23. mov cl,byte[ebx]
  24. mov byte[ebx],al
  25. mov byte[edx],cl
  26. cmp edi,1
  27. jne .bucle
  28. popf
  29. popad
  30. ret
  31. endp
  32. ;Función que retorna el byte menor en al y su posicion en edx
  33. proc Menor,cNumer,cCantidad
  34. push ecx
  35. mov eax,[cNumer]
  36. mov edx,eax
  37. mov ch,byte[eax]
  38. dec eax
  39. .bucle:
  40. dec [cCantidad]
  41. inc eax
  42. .if byte[eax] < ch
  43. mov ch,byte[eax]
  44. mov edx,eax
  45. .endif
  46. cmp [cCantidad] ,0
  47. jne .bucle
  48. mov eax, [cNumer]
  49. mov al,ch
  50. pop ecx
  51. ret
  52. endp
  53.  
  54. .end start                                                            
« Última modificación: 27 Junio 2009, 06:38 am por YST » En línea



Yo le enseñe a Kayser a usar objetos en ASM
ny0x


Desconectado Desconectado

Mensajes: 336


Ver Perfil
Re: [ASM]Algoritmo de Ordenacion Quicksort
« Respuesta #9 en: 26 Junio 2009, 19:20 pm »

bien ya tenemos dos algoritmos de ordenacion  :)

Yurix publicalo si quieres pero no creo que se gane nada con ponerlo en wikipedia  :xD
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Reto Batch]Algoritmo Quicksort
Scripting
Binary_Death 3 3,911 Último mensaje 23 Julio 2012, 02:10 am
por AgnesBlack
Problemas al intentar hacer mas eficiente un algoritmo de ordenacion « 1 2 »
Programación C/C++
Dark00 10 5,770 Último mensaje 14 Noviembre 2012, 23:24 pm
por Dark00
Algoritmo de ordenación.
Programación C/C++
Leafar77 1 1,976 Último mensaje 11 Marzo 2015, 17:16 pm
por NOIS
Ayuda algoritmo de ordenacion
Programación C/C++
0and6 2 2,078 Último mensaje 1 Agosto 2015, 07:27 am
por 0and6
Algoritmo Quicksort aplicado a una QTableWidget en Qt Creator
Programación C/C++
josemanuelbarajas998 2 2,468 Último mensaje 16 Septiembre 2017, 22:34 pm
por josemanuelbarajas998
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines