I have been working on this assignment for couple weks (aling with my other classwork) and I couldn't get it anywhere, can any one help me doing it. Or can you at least tell me hints and tips toward resolving the program: the question is:

The element selection problem is defined here as follows. Given a sequence S = {s1, s2, s3, ..., sn} of integers and an integer k, where 1 ≤ k ≤ n, find the k-th smallest integer in S. The outline of a recursive algorithm that can solve the selection problem follows (adapted from: S. Akl, The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989). The parameter Q in procedure SELECT is a small integer constant.procedure SELECT(S,k)

```
if | S | < Q then sort S and return the k-th elementelse subdivide S into | S | / Q subsequences of Q elements eachend if.
Sort each subsequence and determine its median.
Call SELECT recursively to find m, the median of the | S | / Q medians found in 2.
Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and larger than m, respectively.
if | S1| ≥ k then call SELECT recursively to find the k-th element of S1else if | S1| + | S2| ≥ k then return melse call SELECT recursively to find the (k - | S1| - | S2|)-th element of S3end if
end if.
```

The running time of SELECT is O(n) for any value of Q ≥ 5 (under this condition, recursive calls are carried out for sequences ever-decreasing in size).

Notice the similarities between SELECT and the popular QUICKSORT algorithm. The latter algorithm is for sorting, and has worst case and expected running times O(n2) and O(n lgn), respectively.

I used bubble sort in my code. and my code is the following:* I Also Uploaded the code in a text file *

CODE

```
.data
se: .word 14,23,17
.text
sa: .space 50
sb: .space 50
sc: .space 50
.globl main
main:
la $a0, se #a0 refers to se
addi $s0, $zero,5 #Q
addi $s1, $zero,2 #K
add $s2, $zero,$zero #set s2 to zero
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# count
ct: lw $a1, 0($a0) #store the first word from a0 to a1
add $s2, $s2, 1 #add one to s5 (this is the counter)
addi $a0, $a0, 4 #go to the next word (shift index by 4bytes)
bne $a1, $zero, ct #if a1 is not at the end, go back to ct (count)
la $a0, se #make a0 refers back to beginning of se
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# compare and branch
bgt $s0,$s2,bbss #if Q > |S| then bubble sort and give K
j subs #otherwise, go to subs
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# finish the program
li $v0,10 # exit
syscall
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# bubble sort
bbss: addi $sp,$sp,-4 #adjust this MF for one element
sw $ra,0($sp)
bbs: addi $t0,$s2,0
addi $t0,$t0,-1 #$t0 = na - 1
la $t1,se # pointer pa, $t1 = address of a
li $t2,0 # exchange flag, $t2 = 0
loop:
beq $t0,$zero,done
lw $t6,0($t1) # $t6 = *(pa)
lw $t7,4($t1) # $t7 = *(pa+1)
slt $t3,$t6,$t7 # if ($t6 < $t7)
beq $t3,$zero,next # goto next
sw $t6,4($t1) #
sw $t7,0($t1) # *pa <-> *(pa+1)
li $t2,1 # set exchange flag
next: addi $t1,$t1,4 # pa++
addi $t0,$t0,-1 # $t0 = $t0 -1
j loop
done:
bne $t2,$zero,fin # if (exchange) goto main
fin: la $a0,se
sll $s1,$s1,2
add $s1,$a0,$s1
lw $s3,0($s1)
lw $ra,0($sp)
addi $sp,$sp,4
jr $ra
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# subs
# make em
addi $t0,$s0,0 #copy Q to t0
addi $t1,$s2,0 #copy counter to t1
div $t1,$t0 #to find how many time we have to split
sll $t2,$t0,2 #t2 now contains a shift amount = size of elements
la $t3,se #address of se into a0
again: addi $sp,$sp,-4 #adjust this pointer for 1 element
sw $t3,0($Sp) #store one element on it
add $t3,$t3,$t2 #add size of Q elements
subi $t1,$t1,1 #we did that once, so we subtract
bne $t1,$zero,again
addi $sp,$sp,-4 #adjust this pointer for 1 element
sw $t3,0($Sp) #store one bitch on it
# sort em
sort: addi $t0,$s0,0 #copy Q to t0
addi $t0,$t0,-1 #$t0 = na - 1
lw $t1,0($sp) #load the address of first section
addi $sp,$sp,4 #so we go to next section at next time
li $t2,0 # exchange flag, $t2 = 0
lop:
beq $t0,$zero,pull
lw $t6,0($t1) # $t6 = *(pa)
lw $t7,4($t1) # $t7 = *(pa+1)
slt $t3,$t6,$t7 # if ($t6 < $t7)
beq $t3,$zero,next # goto next
sw $t6,4($t1) #
sw $t7,0($t1) # *pa <-> *(pa+1)
li $t2,1 # set exchange flag
next: addi $t1,$t1,4 # pa++
addi $t0,$t0,-1 # $t0 = $t0 -1
j lop
#////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
# Pull K
pull:
```

- I Also Uploaded the code in a text file *

I would appreciate it

regards

*Edited 3 Years Ago by pritaeas*: Fixed formatting