Assignment #7

Purpose:    Write a simple assembly language program to sort a list of numbers. Learn to use addressing modes, arithmetic operations, and control instructions.

Points:    120


Assignment:
Write a simple assembly language program to sort a list of integer numbers into ascending (small to large) order. To sort the numbers, use the following Gnome sort1 algorithm:

gnomeSort(a[0..size-1]) {

i = 1
j = 2
while (i < size)
if (a[i-1] <= a[i])
i = j
else j = j + 1
swap a[i-1] and a[i]

i = i - 1
if (i = 0)
i = 1

}

The Gnome Sort is based on the technique used by Dutch gardeners to sort a line of flower pots. Basically, the gardener looks at the flower pot next to him and the previous one; if they are in the right order the gardener steps one pot forward, otherwise he

swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forward; if there is no pot next to him, he is done.

You must use the above Gnome sort algorithm (i.e., do not use a different sort). Note, the algorithm assumes array index’s start at 0. If necessary, you can define additional variables. Submissions not based on this algorithm will not be scored.

Additionally, develop three macros as follows:

findSumAve - calculate sum and average
findMinMax - calculate minimum and maximum findMid - calculate median value

The macros are called in the provided main after the list is sorted (i.e., max=list[len-1] and min=list[0]). Note, for an odd number of items, the median value is defined as the middle value. For an even number of values, it is the integer average of the two middle values. The median must be determined after the list is sorted.

You are provided a template for this assignment.





1    For more information, refer to: http://en.wikipedia.org/wiki/Gnome_sort
Submission:
    • All source files must assemble and execute on Ubuntu with yasm.

    • Submit source files
        ◦ Submit a copy of the program source file via the on-line submission

    • Once you submit, the system will score the project and provide feedback.
        ◦ If you do not get full score, you can (and should) correct and resubmit.
        ◦ You can re-submit an unlimited number of times before the due date/time.

    • Late submissions will be accepted for a period of 24 hours after the due date/time for any given lab. Late submissions will be subject to a ~2% reduction in points per an hour late. If you submit 1 minute - 1 hour late -2%, 1-2 hours late -4%, … , 23-24 hours late -50%. This means after 24 hours late submissions will receive an automatic 0.


Program Header Block
All source files must include your name, section number, assignment, NSHE number, and program description. The required format is as follows:

    • Name: <your name>
    • NSHE ID: <your id>
    • Section: <section>
    • Assignment: <assignment number>
    • Description: <short description of program goes here>

Failure to include your name in this format will result in a loss of up to 10%.


Scoring Rubric
Scoring will include functionality, code quality, and documentation. Below is a summary of the scoring rubric for this assignment.

Criteria
Weight
Summary
Assemble
-
Failure to assemble will result in a score


of 0.



Program Header
5%
Must include header block in the


required format (see above).



General Comments
15%
Must include an appropriate level of


program documentation.



Program Functionality
80%
Program must meet the functional
(and on-time)

requirements as outlined in the


assignment. Must be submitted on time


for full score.



Data Declarations:
Refer to the provide main for the provided data declarations.

lst
dd
123,
42, 146,
76, 120,
56, 164,
65,
155,
57

dd
111,
188,
33,
05,
27,
101, 115,
108,
13, 115

dd
17,
26,
129,
117, 107,
105, 109,
30,
150,
14

dd
147,
123,
45,
40,
65,
11,
54,
28,
13,
22

dd
69,
26,
71,
147,
28,
27,
90,
177,
75,
14

dd
181,
25,
15,
22,
17,
1,
10,
129,
12, 134

dd
61,
34,
151,
32,
12,
29, 114,
22,
13, 131

dd
127,
64,
40,
172,
24,
125,
16,
62,
8,
92

dd
111,
183,
133,
50,
2,
19,
15,
18,
113,
15

dd
29,
126,
62,
17, 127,
77,
89,
79,
75,
14

dd
114,
25,
84,
43,
76,
134,
26,
100,
56,
63

dd
24,
16,
17,
183,
12,
81, 320,
67,
59, 190

dd
193,
132,
146,
186, 191,
186, 134,
125,
15,
76

dd
67,
183,
7,
114,
15,
11,
24,
128,
113, 112

dd
24,
16,
17,
183,
12,
121, 320,
40,
19,
90

dd
135,
126,
122,
117, 127,
27,
19,
127,
125, 184

dd
97,
74,
190,
3,
24,
125, 116,
126,
4,
29

dd
104,
124,
112,
143, 176,
34, 126,
112,
156, 103

dd
69,
26,
71,
147,
28,
27,
39,
177,
75,
14

dd
153,
172,
146,
176, 170,
156, 164,
165,
155, 156

dd
94,
25,
84,
43,
76,
34,
26,
13,
56,
63

dd
147,
153,
143,
140, 165,
191, 154,
168,
143, 162

dd
11,
83,
133,
50,
25,
21,
15,
88,
13,
15

dd
169,
146,
162,
147, 157,
167, 169,
177,
175, 144

dd
27,
64,
30,
172,
24,
25,
16,
62,
28,
92

dd
181,
155,
145,
132, 167,
185, 150,
149,
182,
34

dd
81,
25,
15,
9,
17,
25,
37,
129,
12, 134

dd
177,
164,
160,
172, 184,
175, 166,
62,
158,
72

dd
61,
83,
133,
150, 135,
31, 185,
178,
197, 185

dd
147,
123,
45,
40,
66,
11,
54,
28,
13,
22

dd
49,
6,
162,
167, 167,
177, 169,
177,
175, 164

dd
161,
122,
151,
32,
70,
29,
14,
22,
13, 131

dd
84,
179,
117,
183, 190,
100, 112,
123,
122, 131

dd
123,
42,
146,
76,
20,
56,
64,
66,
155,
57
len
dd
39,
126,
62,
41, 127,
77, 199,
79, 175,
14

dd
350









min
dd
0









med
dd
0









max
dd
0









sum
dd
0









avg
dd
0










As necessary, you can define additional variables.


Debugging Tips
    • Use comments!!
    • Follow the algorithm directly (do not attempt to optimize).
    • Comment each part of the algorithm (so you can match the algorithm to the appropriate subset of code).
    • Develop a debugger input file first (based on previous ones) carefully verifying the debugger commands based on the specific data types/sizes.
    • You can temporarily change the array length to a smaller number (i.e., 5-10) for testing.