RSS Feed

Sa utilizam bubble sort …

December 29th, 2007
Posted in Programare(Visual C++)

M-am gandit sa ma mai joc putin cu bubble sort-ul, sa-l folosesc in cadrul unei anumite probleme. Problema care mi-a venit in minte este urmatoarea : Sa se scrie o functie care primeste ca parametru un numar natural si care returneaza cel mai mare numar care se poate forma cu cifrele sale . Algoritmul banal cu care se rezolva aceasta problema este urmatorul:

-retinem cifrele numarului intr-un vector
-le ordonam
-compunem noul numar

Am implementat totul in ASM desigur. Pentru a nu mai recurge la fel de fel de artificii, am organizat vectorul in felul urmator:
v[0] - numarul de cifre
v[1] ... v[v[0] - cifrele numarului

Bineinteles, am modificat usor bubble-sort-ul ( cel scris de mine avea nevoie de 2 variabile , un pointer catre primul element al vectorului, v[0] , si numarul de elemente ... cateva modificari minore si a fost gata. O alta problema care mi-a atras atentia la bubble sort a fost urmatoarea : ce se intampla daca exista un singur element in vector ? Am vrut sa merg la f**** masa si sa-l las asa, dar atunci cand compara v[i] cu v[i+1], sare la o adresa la care nu se gaseste nimic ... eroare :) ... am prevazut acest caz in functia maxim() . Este cel mai lung programel scris de mine in ASM ( vreo 90 linii de cod ) ... Sper sa nu mai am placerea sa scriu programe atat de lungi in ASM, e foarte dificil sa caut erori, chiar si cu ajutorul debugger-ului ... Iata codul...

PLAIN TEXT
C++:
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void bubble_sort(int*)
  5. {
  6.     _asm
  7.     {
  8. bucla_mare:
  9.         mov ecx,0
  10.         mov eax,[ebp+8]
  11.         mov ebx,[eax]
  12.         add eax,4
  13. bucla_mica:
  14.         mov edx,eax
  15.         add edx,4
  16.         mov esi,[eax]
  17.         cmp esi,[edx]
  18.         ja interschimbare
  19.         jmp continua
  20. interschimbare:
  21.         push dword ptr [edx]
  22.         push dword ptr [eax]
  23.         pop dword ptr [edx]
  24.         pop dword ptr [eax]
  25.         mov ecx,1
  26.         jmp continua
  27. continua:
  28.         add eax,4
  29.         dec ebx
  30.         cmp ebx,1
  31.         jne bucla_mica
  32.         cmp ecx,1
  33.         je bucla_mare
  34.     }
  35. }
  36.  
  37. int maxim(int)
  38. {
  39.     int v[12];
  40.     _asm
  41.     {
  42.         mov eax,[ebp+8]
  43.         cmp eax,10
  44.         jb exceptie
  45.         jmp continua
  46. exceptie:
  47.         mov ecx,eax
  48.         jmp stop2
  49. continua:
  50.         mov ebx,10
  51.         mov ecx,0
  52.         lea esi,v
  53.         add esi,4
  54. bucla1:
  55.         mov edx,0
  56.         cmp eax,0
  57.         je stop1
  58.         div ebx
  59.         inc ecx
  60.         mov [esi],edx
  61.         add esi,4
  62.         jmp bucla1
  63. stop1:
  64.         lea eax,v
  65.         mov [eax],ecx
  66.         push eax
  67.         call bubble_sort
  68.         add esp,4
  69.  
  70.         mov ecx,0
  71.         mov eax,1
  72.         lea esi,v
  73.         mov ebx,[esi]
  74.         add esi,4
  75. bucla2:
  76.         cmp ebx,0
  77.         je stop2
  78.         push ecx
  79.         mov ecx,[esi]
  80.         mov edx,0
  81.         push eax
  82.         mov edi,eax
  83.         mov eax,1
  84.         mul edi
  85.         mul ecx
  86.         pop edx
  87.         pop ecx
  88.         push edx
  89.         add ecx,eax
  90.         pop eax
  91.         mov edi,10
  92.         mul edi
  93.         dec ebx
  94.         add esi,4
  95.         jmp bucla2
  96. stop2:
  97.         mov eax,ecx
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     int x;
  104.     cin>>x;
  105.     cout<<maxim(x)<<endl;
  106.     system("pause");
  107.     return 0;
  108. }

Leave a reply...