You are asked to implement the radix sort algorithm using MIPS assembly language

Question

You are asked to implement the radix sort algorithm using MIPS assembly language.

Suppose that initially you are given an array with unsorted unsigned numbers. Radix sort sorts numbers by processing individual digits and can process digits of each number either starting from the least significant (LSD) or the most significant digit (MSD). We will use LSD sorting. During the first pass in LSD, numbers in the array are grouped based on the least significant digit. During the second pass, numbers are grouped again using the last but one least significant digit but otherwise keeping the original order of numbers. This operation is continued until numbers are grouped for all digits with the final result being the sorted array.

Here, you can find the C and Java implementations of Radix Sort with comments. http://www.geeksforgeeks.org/radix-sort/

Radix sort uses counting sort as a subroutine to sort. The number of occurrences for each digit at the corresponding position is counted and stored in the dedicated array “count”. Then using count array the absolute position for each group of digits within array is calculated. Next, numbers are placed into temporary array (“output”) at the locations specified by corresponding values. Finally output array is copied to the original array

Initial array Pass 1 Pass 2 Pass 3 Pass 4

You may find the animated video that explains radix sort useful: https://www.youtube.com/watch?v=dHeTp6hO71U

Your program should print the sorted array to the standard output.

Explanation / Answer

phase 1:               step 1           step 2                                step3                         step 4

                             count[0]=3          count[0]=3                       count [0]=5              count[0]=5

                             count[1]=4         count[1]=4                        count[1]=2                   count[0]=2

phase 2:          abspos[0]=0           abspos[0] =0                         abspos[0]=0                   abspos[0]=0                

                     abspos[1]=3               abspos[1]=3                              abspos[1]=5                        abspos[1]=5

Example of least significant digit radix?2 sort with counting passes for 4?bit numbers.

program:

#define N 1000;

#define logradix 1;

#define wordwidth 32;

unsigned int array[N];

unsigned int arraytemp[N];

int count[2^logradix];

int abspos[2^logradix];

int i, j, k;

radixmask = 2^logradix ?1;

for(j=0; j<wordwidth; j=j+logradix) {

/* phase 1: to perform the counting*/

for(k=0;k<2^logradix;k++) /* initialize values of count array elements to zero */

count[k]=0;

for(i=0;<N; i++)   /* to count number of times each digit occur in an array occurs*/

count[(array[i]>>j*logradix)&&radixmask]++;

/* phase 2tto calculate absolute position for each digit */

for (k=0; k<2^logradix; k++) abspos[k] = 0;           /* initialize values of abspos array to zero */

for (k=0; k<2^logradix?1; k++) abspos[k+1]=abspos[k] +count[k];     /* calculate the absolute position of the digit */

/* phase 3:to perform the sorting */

for (i=0; i < N; i++) {

curradix = (array[i]>>j*logradix)&&radixmask;

arraytemp[abspos[curradix]++] = array[i];    /* place into arraytemp to the corresponding position */

}

/ * copy arraytemp to array */

for (i=0; i < N; i++) array[i] = arraytemp[i];

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.