In this project, you are expected to implement a bubble sort algorithm in assemb

Question

In this project, you are expected to implement a bubble sort algorithm
in assembly language, evaluate its performance, and compare the
performance with that of your C++ implementation.

You are required to implement bubblesort in a separate
procedure instead of in the main function.
2. To compare the performance, you need to write the main
program to generate random numbers to populate a large
integer array, and then call the subroutine to sort this array.
Remember to get the time before and after the bubble sort to
measure the performance.
Refer to the Irvine32 library documentation to see how to generate
random numbers and how to get time.

Explanation / Answer

Let's start with the algorithm. To sort an array of numbers, you compare 1st number to the 2nd number and swap their places if the 2nd number is higher. Then you do the same thing for the 2nd and 3rd numbers and then repeat the comparisons until you've compared all of the pairs in the array. Of course, just going through the comparisons only once is not enough to sort the whole array. You need to repeat the comparisons a certain number of times until the array is completely sorted. You also should know how many comparisons to make for a given number of numbers in an array. If you work out with some test numbers on paper, you will find that the number of paired comparisons to do is equal to the number of array numbers minus 1. The maximum number of times you have to repeat the comparison process is equal to the number of array numbers minus 1.

Okay, now we have a working algorithm. Now work it out in pseudo-code. The psedo-code below assumes that it is okay to change your array of numbers, so a second "destination" array is not used.

1) Set a pointer to the start of the array.
2) Get the number that the pointer points to and also get the next number.
3) Compare the two.
4) If the next number is greater than the 1st number, then swap places.
5) Increment the pointer.
6) Are we done with all the comparisons? (number of array numbers -1)
7) If not, then loop back to step 2.
8) Are we done with the number of inner loops? (number of array numbers - 1)
9) If not, go back to step 1.

Okay, now we have to write the pseudo-code as x86 assembly language code.
The pseudo-code shows that we need 2 loops. Whenever you are working with nested loops, it is best to make the inner loop FIRST. The outer loop just repeats the inner loop, so the inner loop code is what you should concentrate on.

;inner loop
mov si,2000h ;array of 7 numbers starts at address 2000h (2000 hex)
mov cx,6 ;CX is our counter for the number of comparisons

inner_loop:
mov ax, word ptr [si] ;get two numbers
cmp al,ah ;(AL contains the 1st number and AH contains the 2nd number)
jb exchange ;jump if we need to exchange their places
inc si ;increment our pointer
dec cx ;decrement comparison counter
jnz inner_loop ;continue loop if CX isn't zero
jmp done ;jump to done if no more comparisons

exchange:
xchg al,ah ;swap the values in AL and AH
mov word ptr [si],ax ;write the pair back to the array
inc si ; increment array pointer
dec cx ;decrement comparison counter
jnz inner_loop ;continue loop or drop down to 'done'

done:
;program exit code goes here

I already know that the code works, but you should verify your own code before adding the code for the outer loop. Here's my code:

mov dx,6 ;DX is our outer loop counter

outer_loop:
mov si,2000h ;array starts at address 2000h (2000 hex)
mov cx,6 ;CX is our counter for the number of comparisons

inner_loop:
mov ax, word ptr [si] ;get two numbers
cmp al,ah ;(AL contains the 1st number and AH contains the 2nd number)
jb exchange ;jump if we need to exchange their places
inc si ;increment our pointer
dec cx ;decrement comparison counter
jnz inner_loop ;continue loop if CX isn't zero
dec dx ;decrement outer loop counter
jnz outer_loop
jmp done ;jump to "done" if no more comparisons

exchange: ;this code is run if we need to swap the values
xchg al,ah ;swap the values in AL and AH
mov word ptr [si],ax ;write the pair back to the array
inc si ; increment array pointer
dec cx ;decrement comparison counter
jnz inner_loop ;continue loop or drop down to outer loop check
dec dx ;decrement outer loop counter
jnz outer_loop ;if DX isn't 0, then go to outer_loop (reset pointer and CX)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.