Ordinamento vettore di interi

di
Enrichetto
il
22 risposte
E
Enrichetto
Utente Attivo
Iscritto da
feb, 2017
Messaggi:
52

Ordinamento vettore di interi

Salve a tutti,
perdonatemi se apro un'altra discussione in breve tempo (non vorrei approfittarne) però preferisco affrontare i dubbi quando sono freschi.
Sto cercando di scrivere un programma in assembly che ordini un vettore di interi. Ho utilizzato il selection sort (o meglio, mi sono ispirato ad esso) ma il vettore non viene ordinato.
Facendo qualche test mi sembra di capire che il problema sia che non supera il primo valore (forse sbaglio le condizioni di fine vettore poiché applico le stesse regole usate per le stringhe e cioè terminatore 0).

Metto il codice C e Assembly: 
void main(){
	int vettore[]={1,5,2,30,-7,12};
	ordina_vettore(vettore);
	getchar();
}
.586
.model flat
.code

_ordina_vettore proc
push ebp
mov ebp,esp

push eax
push ebx
push ecx
push edx
push esi
push edi

mov eax,dword ptr[ebp+8]	;Vettore
mov esi,0					;contatore i
mov edi,0					;contatore j


;vettore vuoto
cmp byte ptr[eax],0
je FINE



CICLO1:
cmp byte ptr[eax+esi],0
je FINE

mov edi,esi
inc edi
mov bl,byte ptr[eax+esi]	;bl è il valore minimo: lo inizializzo al primo valore


CICLO2:
cmp byte ptr[eax+edi],0
je FINECICLO2

cmp byte ptr[eax+edi],bl
jl MINIMO
inc edi
jmp CICLO2



;se ho trovato un valore minore inverto subito i valori
MINIMO:
mov cl,byte ptr[eax+esi]
mov byte ptr[eax+esi],bl
mov byte ptr[eax+edi],cl
inc edi
jmp CICLO2

FINECICLO2:
inc esi
jmp CICLO1



FINE:
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax

mov esp,ebp
pop ebp

ret
_ordina_vettore endp
end
Non capisco dove (e quanto) sbaglio

Grazie in anticipo a chiunque vorrà aiutarmi

22 Risposte

  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    Ho fatto altre prove ma non riesco a sistemarlo..e credo che neanche voi sappiate aiutarmi con quel codice da me scritto

    Quindi modifico il quesito:
    Ho a disposizione i registri: eax,ebx,ecx,edx,esi,edi ma le variabili su cui devo lavorare sono più di 6 quindi mi sembra chiaro che sbaglio qualcosa nell'associazione delle variabili.
    Nel caso particolare in cui la funzione invia il vettore e il numero degli elementi, in lettura avrò: 
    mov eax, dword ptr[ebp+8]		;lettura vettore di interi
mov bx, word ptr[ebp+12]		;lettura numero elementi del vettore (intero)
    Per l'algoritmo dell'ordinamento mi servono 2 contatori (di tipo intero), quindi utilizzerò esi e edi.
    Un contatore andrà da 0 a N (bx) ma un altro andrà fino a (N-1) quindi mi serve un'altra variabile che memorizzi (N-1) (facciamo ECX)

    Mi serve inoltre memorizzare l'indice del più piccolo valore trovato e quindi mi serve un'altra variabile-registro (facciamo che utilizzo il registro EDX).
    Per scambiare i valori dovrò anche memorizzare il valore del vettore che andrò a modificare e quindi mi serve un'altra variabile-registro (quale?).

    Quindi ho 6 registri (che utilizzo sicuramente male) e 7 variabili. Non fate caso al tipo di algoritmo che utilizzo ed alle possibili modifiche che potrei fare al codice per ridurre il numero di variabili: ho altri esercizi in cui si presenta lo stesso problema quindi vorrei concentrarmi proprio sulla questione variabili>registri
    Sapete dirmi come risolvere il problema?


    Spero che ci sia qualcuno in grado di aiutarmi vi ringrazio in anticipo!
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    Enrichetto ha scritto:

    neanche voi sappiate aiutarmi con quel codice da me scritto
    Più che altro quel codice andrebbe rifatto tutto ...

    Tu conosci il bubble sort come algoritmo di ordinamento?
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    oregon ha scritto:

    Tu conosci il bubble sort come algoritmo di ordinamento?
    Si certo, conosco i principali algoritmi di ordinamento. Avevo scelto il Selection Sort perché è quello più vicino al pensiero umano quindi più intuitivo per iniziare ad ordinare in un nuovo (per me) linguaggio.

    oregon ha scritto:

    Più che altro quel codice andrebbe rifatto tutto ...
    Del codice da me postato, eliminando la parte che va da CICLO1 a FINECICLO2 (quindi eliminando la funzione vera e propria) ci sono errori? Non ho capito se commetto ancora errori nell'intestazione e chiusura del file.

    Inoltre mi interessa ancora capire la questione delle variabili in numero maggiore dei registri disponibili.

    Grazie mille!
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    Guarda ... dopo un po' mi sono perso nel tuo codice ... non va bene ...

    I registri e le variabili non devono essere di egual numero, esiste la memoria e lo stack da usare temporaneamente.

    Il bubble sort mi sembra più semplice del selection sort. Proverei con quello per iniziare.
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    oregon ha scritto:

    Il bubble sort mi sembra più semplice del selection sort. Proverei con quello per iniziare.
    Ok! Ora provo ad implementarlo e posto qui i risultati (magari potrà servire a qualcuno )

    oregon ha scritto:

    I registri e le variabili non devono essere di egual numero, esiste la memoria e lo stack da usare temporaneamente.
    Quindi nella pratica, se io dovessi memorizzare:
    - un vettore di interi
    - un intero (lunghezza del vettore)
    - un intero (lunghezza del vettore sottratta di 1 unità)
    - due contatori (per due cicli innestati)
    - un intero (un indice del vettore)
    - un valore intero
    come dovrei fare?
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    Il vettore e la lunghezza stanno in memoria.

    Per i contatori puoi usare due registri, un registro e una locazione di memoria, un registro lo stack, due locazioni di memoria ...

    E così via ... dipende da come si evolve il codice ...

    Non sonno questi i problemi, non ti bloccare su questi dettagli. Imposta uno pseudocodice e parti da quello.
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    Usando il Bubble Sort ho ancora qualche problema, ecco il codice: 
    .586
.model flat
.code

_ordina_vettore proc
push ebp
mov ebp,esp

push eax
push ebx
push ecx
push edx
push esi
push edi

mov eax,dword ptr[ebp+8]	;Vettore
mov ebx,dword ptr[ebp+12]	;numero elementi
mov esi,0					;contatore i
mov edi,0					;contatore j


;BUBBLE SORT
;for(i = 0; i<n-1; i++) {
;	for(k = 0; k<n-1-i; k++) {
;         if(v[k] > v[k+1]) {
;			temp = v[k];
;			v[k] = v[k+1];
;			v[k+1] = temp;
;         }
;	}
;}


;vettore vuoto
cmp ebx,0
je FINE

CICLO1:
;condizione i<n-1 -> i+1<n
inc esi
cmp esi,ebx
je FINE
dec esi


CICLO2:
;condizione k<n-1-i -> k+i+1<n
add edi,esi
inc edi
cmp edi,ebx
je FINECICLO2
sub edi,esi
dec edi

mov cl,byte ptr[eax+edi]
cmp cl,byte ptr[eax+edi+1]
jg SCAMBIA

inc edi
jmp CICLO2


FINECICLO2:
inc esi
mov edi,0
jmp CICLO1

SCAMBIA:
mov dl,byte ptr[eax+edi+1]
mov byte ptr[eax+edi],dl
mov byte ptr[eax+edi+1],cl
inc edi
jmp CICLO2

FINE:
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax

mov esp,ebp
pop ebp

ret
_ordina_vettore endp
end
    Sembra funzionare tutto bene ma i valori di cl e dl sono sempre errati (0 o 1) e non capisco il motivo.

    Questa funzione mi sta davvero facendo impazzire :\
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    E' più semplice implementare questa versione del Bubble Sort
    
	int flag, temp, i;
	do
	{
		flag = 0; 

		for (i = 0; i < n- 1; i++)
			if (vett[i] > vett[i + 1])
			{
				temp = vett[i];
				vett[i] = vett[i + 1];
				vett[i + 1] = temp;
				flag = 1; 
			}
	} while (flag == 1);
    in cui n è il numero di elementi del vettore.
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    Ok utilizzo quel codice.

    Premetto che sono un po' fuso (è da 48h praticamente che studio/programmo in assembly al pc) ma mi sono bloccato in un punto: 
    .586
.model flat
.code

_ordina_vettore2 proc
push ebp
mov ebp,esp

push eax
push ebx
push ecx
push edx
push edi
push esi

mov eax,dword ptr[ebp+8]		;vettore
mov ebx,dword ptr[ebp+12]	;numero elementi
mov esi,0						;contatore i
mov edi,0						;flag


CICLO:
;i<n-1 -> i+1<n
inc esi
cmp esi,ebx
jge FINE
dec esi


mov dx,word ptr[eax+esi]
cmp dx,word ptr[eax+esi+1]
jg SCAMBIA

inc esi
jmp CICLO
    La quintultima riga mi da il problema. Voglio prendere il termine del vettore che si trova in quella posizione (vettore per intenderci). Quel valore è un intero e quindi occupa 2 byte e dunque devo caricarlo come word in un registro dx (o cx o quel che mi pare..) giusto?
    Se sono riuscito a non far errori in questa riga, come mai mi legge correttamente il primo valore (vettore[0]) ma dal secondo ciclo (vettore[1], vettore[2],...) mi legge 0, fino a darmi errore?
    Non tocco nessun registro implicato al ciclo (in SCAMBIA ripeto semplicemente il ciclo, nessun'azione). Non ne capisco il senso..
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    Gli int in questo ambiente sono a 4 byte (32 bit) a meno che tu non chiami il programma passando un vettore di short int
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    oregon ha scritto:

    Gli int in questo ambiente sono a 4 byte (32 bit) a meno che tu non chiami il programma passando un vettore di short int
    Anche così non funziona: ho utilizzato questo codice 
    CICLO:
cmp esi,ebx
jge FINE

mov edx,dword ptr[eax+esi]  ;provato anche con mov edx,dword ptr[eax+esi*4] e mov edx,dword ptr[eax+esi*2] 

inc esi
jmp CICLO
    e al primo ciclo edx contiene il valore di vettore[0] ma dal secondo ciclo ottengo valori assurdi (al secondo ciclo questo è il valore del debug per edx: 4261412864, tipo unsigned long)

    Riesci a capire cosa sbaglio?
    Sto impazzendo per un'unica riga di codice
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    EDIT: piccolo aggiornamento: mettendo 
    mov edx,dword ptr[eax+esi*4]
    vengono letti i valori senza segno ma ottengo valori assurdi in quelli negativi.
    Ad esempio il mio vettore è: 
    int vett[]={4,-2,5,11,6,30};
    Il primo valore viene letto, il terzo, quarto, quinto e sesto pure. Al secondo valore invece viene letto un numero assurdo (edx = 4294967294)

    Quindi il problema ora è solo la lettura dei numeri con segno (negativo)

    Help!
    Grazie ancora!!
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21245

    Re: Ordinamento vettore di interi

    Guarda che quel valore è corretto. In esadecimale corrisponde a FFFFFFFE ovvero a -2 espresso in complemento a 2 (che dovresti sapere cosa è ...).

    Insomma, probabilmente non sai come vengono rappresentati i valori interi negativi in binario ...
  • E
    Enrichetto
    Utente Attivo
    Iscritto da
    feb, 2017
    Messaggi:
    52

    Re: Ordinamento vettore di interi

    oregon ha scritto:

    Guarda che quel valore è corretto. In esadecimale corrisponde a FFFFFFFE ovvero a -2 espresso in complemento a 2 (che dovresti sapere cosa è ...).

    Insomma, probabilmente non sai come vengono rappresentati i valori interi negativi in binario ...
    Ovviamente conosco la rappresentazione in complemento a 2 (è un argomento che si studia al primo anno) ma non avevo pensato di osservare quel valore in hex.

    Tutto risolto! Grazie
Devi accedere o registrarti per scrivere nel forum
22 risposte