Say we have a diamond (85 elements in a 13*13 array)
Every element has two parameters, a/b
We need to sort the diamond so that:
- the [a] parameter increases in each column.
- the [b] parameter increases in each row.
What we want to get is like this: (the * is the part that is not defined in memory)
(this is an easy one 13 elements in a 5*5 array)
original:
* * 4/3 * *
* 1/3 2/3 4/5 *
1/2 3/1 2/5 3/6 2/7
* 2/3 1/2 5/2 *
* * 6/1 * *
sorted:
* * 1/3 * *
* 1/2 2/3 2/5 *
1/2 2/3 4/5 3/6 2/7
* 3/1 5/2 4/3 *
* * 6/1 * *
My algorithm is to bubble sort (according to a) all the values, then sort in each line according to the b parameter. This works pretty good but the dynamic instructions would be over 80000 (which should be O[n^2]). The bubble sort sucks hard in MIPS 'cause you need >10 instr. for each check (in bubble).
I want to know if there is better algorithm that reduces the dynamic instructions under 14000. BTW only use <=15 register and <=66 static instructions (which is 66 lines of code).
findnum: addi $27, $27, 4
lw $21, 0($27)
beq $21, $0, findnum # find the next nonzero number
bsort: lw $20, 0($25) # load first number
slt $12, $21, $20 # if second < first $12=1
bne $12, $15, back # $15 is constant 1
sw $21, 0($25)
sw $20, 0($27)
back: addi $25, $27, 0 # now second number is first number
bne $27, $26, findnum # $27 not the end then continue
loop: addi $25, $01, 24
addi $27, $25, 0 # reinitialize the number
addi $10, $10, 1 # i++
bne $10, $11, findnum # if i not equal to 85 jump back
This is the core part of my code. $25 and $27 are initialized as the address of the first value of the array. $26 is the address of the last value.
Thanks a lot!
peter_the_oak :
One approach that allows you to evide the 2D structure is to transform your values, fill them into a 1D array, sort them, fill them back to 2D and transform them back.\n\nSo with your simplified example, this: 4/3 would become the number: 403 by this transformation: \n\nn(x/y) = 100*x + y\n\n\nFilling a 2D array to a 1D array is a simple (nested) for loop, and back again too. \n\n[403, 103, 203, 405 ...]\n\n\nThen, once you have such numbers in a 1D array, just sort it e.g. by Quicksort. \n\nFor copying back 1D to 2D, you should have a rule for which number belongs to which row. The transformation for numbers back would be:\n\n(x/y) = ( floor(n/100) / n%100 )\n\n\nSorting a 2D structure in general, with general criteria, may not be that easy. But in this case, this approach will work. It has been used on other occasions:\n\nSorting with 2D Arrays ",
2014-07-12T05:54:48