Computer Organization and Assembly Languages

Computer Organization and Assembly Languages, Fall 2005

Forum

Jump to...

assignment #1
assignment #2
assignment #3
final project
assignments

Assignment #4: Sorting

Assigned: 2005/12/01
Due: 2005/12/18
grade

Description

Sorting, the most fundamental problem in studing algorithm, refers to reorder a sequence of numbers so that they appear in an ascending order.

In this project, you need to implement one sorting algorithm of your own choice. However, since bubble sort has already been presented in the class, please do not choose bubble sort. The choice of your sorting algorithm should base on what you have learned from your algorithm course. Remember that your grade is partly dependent on the efficiency of your code. If you choose a slow algorithm to start with, it is likely that you will have a slow program at the end no matter how much effort you have put in optimizing your code in assembly level. In addition, when choosing your algorithm, please do not make any assumption about the distribution of the input sequence.

Specification

You have to implement a procedure called "asm_sort" by assembly. This procedure should accept a pointer to an integer array and a number. The elements of this array are 32-bit signed integers, and the second argument is the number of elements. You should put the sorted result into the input array directly. The skeleton should look like

    .386
    .model flat
    option casemap :none
			    
    .code
    _asm_sort PROC PUBLIC
        push ebp
        mov ebp, esp ; build stack frame

	; variables in stack
	; [ebp+12] length of the integer array
	; [ebp+8]  pointer to the integer array
	; [ebp+4]  return address
	; [ebp]    previous ebp

        ; begin sorting
        ; WRITE YOUR OWN CODE HERE

        ; end sorting
        leave
        ret
    _asm_sort ENDP
    END ; file ends here

In hw4.zip, you will find main.cpp where other functions are implemented. They are used to open a file and do timings, and you don't need to modify them. When your work is done in sort.asm, execute "nmake" and the executable file "sort.exe" will be built.

There is also a test data "input.txt", which is suitable for testing your work. Type "sort input.txt" and it will check if your result is correct.

Grading

As always, you will get 80 points if you implement this procedure correctly. Another 0~20 points will be added to your grade depends on the speed of your program and 0~10 points depends on the code size.

Submission

Please send your code to littleshan@cmlab.csie.ntu.edu.tw
The subject should be "[ASSEMBLY] HW4-YOURID", with YOURID replaced by your student ID.
Don't use attachment: copy your blur.asm into the mail body directly, just like mails to ACM judge.