다이아몬드

Question

우리가 다이아몬드 (13 * 13 배열의 85 개 요소)이 말 모든 요소는 두 개의 매개 변수, 우리는 그래서 다이아몬드 정렬 할 필요가 A/B 있습니다

1. 을 각 열에서 [a] 매개 변수가 증가합니다.
2. [b] 매개 변수는 각 행에서 증가합니다.

은 우리가 얻고 싶은 것은 다음과 같이이다 :

(이 5 * 5 배열의 쉬운 13 개 요소입니다)합니다 (* 메모리에 정의되지 않은 부분이다) 원래

:

* * 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 * * 

정렬 :

* * 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 * * 

내 알고리즘은 모든 값을 정렬하여 버블 링 한 다음 b 매개 변수에 따라 각 행을 정렬합니다. 이것은 꽤 잘되지만 동적 인 명령어는 80000 이상이 될 것입니다 (O [n^2]이어야합니다). 버블 정렬은 10 점 이상이 필요하기 때문에 MIPS에서 열심히 짜증납니다. 각 수표마다 (거품으로).

14000 미만의 동적 명령어를 줄이는 더 나은 알고리즘이 있는지 알고 싶습니다. BTW는 < = 15 레지스터와 < = 66 개의 정적 명령어 (66 줄의 코드) 만 사용합니다.

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  

이것은 내 코드의 핵심 부분입니다. $ 25 및 $ 27은 배열의 첫 번째 값의 주소로 초기화됩니다. $ 26은 마지막 값의 주소입니다.

고맙습니다.

Answer 1

2D 구조를 구현할 수있는 한 가지 방법은 값을 변환하고, 1D 배열로 채우고, 정렬하고, 다시 2D로 채우고 다시 변환하는 것입니다. 이 변환에 의해 403 : 4/3는 숫자가 될 것이다 : 이것은 사용자의 단순화 된 예에 따라서

,

n(x/y) = 100*x + y 

1 차원 어레이로 2 차원 배열을 채우는 다시 A (중첩) 단순 루프되고 너무.

그런 다음 1D 배열에 이러한 숫자가 있으면 예를 들어이를 정렬하면됩니다. Quicksort.

1D에서 2D로 복사하려면 숫자가 어느 행에 속해야하는지 규칙이 있어야합니다. 숫자 변환은 다시 다음과 같습니다

(x/y) = (floor(n/100)/n%100) 

이 일반 기준, 일반적으로 2 차원 구조 정렬, 그렇게 쉽게되지 않을 수 있습니다. 그러나이 경우에는이 접근 방식이 효과적입니다.다른 경우에 사용되었습니다

Sorting with 2D Arrays

Answer 2

SortDiamond:  addi $01, $00, Array  # set memory base 
      swi 521   # create sort diamond and update memory 
      addi $06, $00, 6  # constant 6 
      addi $07, $00, 12  # constant 12 
      addi $12, $00, 0  # counter inner 
      addi $21, $00, 0  # counter in bubble 
      addi $22, $00, 0  # bs counter  

bigloop:  addi $20, $01, 72  # find the address first element to sort(row) 
      addi $26, $20, 0 
      addi $10, $00, 1  # i starts from 1  
      addi $11, $00, 2  # sort times 
      addi $23, $00, 2 

bsrow:   lw $17, 0($26) 
      lw $18, 4($26) 
      andi $27, $17, 0x003F  
      andi $28, $18, 0x003F 
      slt $19, $28, $27 
      beq $19, $00, go 
      sw $17, 4($26) 
      sw $18, 0($26) 
      addi $22, $00, 1  # this is the indicator of bubble sort 

go:   addi $26, $26, 4 
      addi $21, $21, 1 
      bne $21, $23, bsrow 

loopi:   addi $12, $12, 1 
      addi $26, $20, 0 
      addi $23, $23, -1 
      addi $21, $00, 0 
      beq $22, $00, loopj  # jump if it doesn't do bubble sort in one loop 
      bne $12, $11, bsrow 

loopj:   addi $10, $10, 1  # i++  
      addi $22, $00, 0  # reinitialize counter 
      slti $19, $10, 7  # find next row 
      beq $19, $00, great  # if i<7 next address is 48+ current 
      sll $11, $10, 1 
      addi $20, $20, 48 
      j less 

great:   sub $11, $07, $10 
      sll $11, $11, 1 
      addi $20, $20, 56 

less:   addi $23, $11, 0  
      addi $26, $20, 0 
      addi $12, $00, 0 
      bne $10, $07, bsrow     
      addi $20, $01, 264 
      addi $26, $20, 0 
      addi $10, $00, 1 
      addi $23, $00, 2 
      addi $11, $00, 2 

bscol:   lw $17, 0($26) 
      lw $18, 52($26) 
      slt $19, $18, $17 
      beq $19, $00, go1 
      sw $17, 52($26) 
      sw $18, 0($26) 
      addi $22, $00, 1 

go1:   addi $26, $26, 52 
      addi $21, $21, 1 
      bne $21, $23, bscol 

loopi1:   addi $12, $12, 1 
      addi $26, $20, 0 
      addi $23, $23, -1 
      addi $21, $00, 0 
      beq $22, $00, loopj1 
      bne $12, $11, bscol 

loopj1:   addi $10, $10, 1 
      addi $22, $00, 0 
      slti $19, $10, 7 
      beq $19, $00, great1 
      sll $11, $10, 1 
      addi $20, $20, -48 
      j less1 

great1:   sub $11, $07, $10 
      sll $11, $11, 1 
      addi $20, $20, 56 

less1:   addi $23, $11, 0  
      addi $26, $20, 0 
      addi $12, $00, 0 
      bne $10, $07, bscol 
      swi  522 
      bne $02, $00, bigloop 
      swi 523   # redisplay diamond 
      jr $31   # return to caller