COMPUTER ASSEMBLY Array Maximum and Minimum Declare an array of integers: .data
ID: 3710362 • Letter: C
Question
COMPUTER ASSEMBLY
Array Maximum and Minimum Declare an array of integers: .data size: .word 8 array: .word 23, -12, 45, -32, 52, -72, 8, 13 Write a program that determines the minimum and the maximum element in the array. Assume that the array has at least one element (in which case, that element will be both the minimum and maximum.) Leave the results in registers. Qtspim simulator: The starting address of Data Section is 0x10000000 Mars simulator: The starting address of Data Section is 0x10010000
Explanation / Answer
/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
int min;
int max;
};
struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;
/* If there is only on element */
if (low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}
/* If there are two elements */
if (high == low + 1)
{
if (arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}
/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);
/* compare minimums of two parts*/
if (mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;
/* compare maximums of two parts*/
if (mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
out put
Time Complexity: O(n)
Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer
If n is a power of 2, then we can write T(n) as:
After solving above recursion, we get
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.
/* structure is used to return two values from minMax() */
#include<stdio.h>
struct pair
{
int min;
int max;
};
struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;
/* If there is only on element */
if (low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}
/* If there are two elements */
if (high == low + 1)
{
if (arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}
/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);
/* compare minimums of two parts*/
if (mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;
/* compare maximums of two parts*/
if (mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;
return minmax;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("nMinimum element is %d", minmax.min);
printf("nMaximum element is %d", minmax.max);
getchar();
}
out put
Time Complexity: O(n)
Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 T(2) = 1 T(1) = 0
If n is a power of 2, then we can write T(n) as:
T(n) = 2T(n/2) + 2
After solving above recursion, we get
T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.