Problem Description: Find the Median of two merged sorted arrays.
This article demonstrates some of the differences in array handling using the C language and the Ada language.
C version:
|
int* merge(int arr1[], size_t len1, int arr2[], size_t len2) { int * const ret = malloc((len1 + len2) * sizeof(int)); // merge the two arrays while they both
have values // fill with any residue from arr2 double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
int *arr = merge(nums1, nums1Size, nums2, nums2Size), len = nums1Size+ nums2Size;
double mid;
if(len % 2 == 1)
{
mid = *(arr + len/2);
}
else
{
mid = (*(arr+len/2)+*(arr+len/2+1))/2.0;
}
free(arr);
return mid;
}
|
The C language provides no way to declare an array type. Furthermore only a pointer to the first element of an array is passed to a function parameter when the programmer specifies the array name to be passed. The second parameter associated with each array passed in this example is the number of elements in the array.
The C language does not provide a general concatenation operator for arrays that works with parameters passed to a function because the general case for an array does not carry any information about the number of elements in the array instance. That information is only available within the scope in which the array instance is declared.
The merge function shown above is a solution to these problems. The programmer is required to write their own array concatenation function.
This C language solution produces a merged, but not necessarily sorted, array.
Ada version:
The Ada language allows subprograms to be defined within other subprograms. The solution below defines the Find_Median function within the Main procedure.
The Find_Median function is shown below.
|
type Flt_Array is array (Positive range
<>) of Float; |
Arrays are first class types. The Ada example declares an unconstrained array type indexed by the subtype Positive. The subtype positive is a subtype of the Integer type. Integer is a signed 32-bit integer with a maximum valid value of 2^31 – 1. Subtype Positive is a constrained subtype of Integer with a minimum value of 1 and a maximum value of 2^31 – 1. Each element of the array is a Float. Unconstrained array types allow instances of the array type to have different numbers of elements. Each instance is constrained in its size.
An Ada array instance passed to a function does not “decay” to a pointer to the first object. All information about the array including its element type, the range of index values, and the number of elements in the array instance are passed with the array.
The Find_Median function takes two parameters of type Flt_Array and returns a Float.
The variable Mid is an instance of the subtype Positive, which is the same type as the array index type.
The Temp variable is an instance of Flt_Array initialized by the concatenation of the array passed to parameter A and the array passed to parameter B. The “&” operator in Ada concatenates two arrays of the same type. The “&” operator plus the sort procedure replace the merge function in the C example.
Ada.Containers.Generic_Array_Sort is a pre-defined generic sort procedure for unconstrained arrays. The parameters passed to the generic sort procedure create a concrete procedure specialized for sorting the Flt_Array type.
The index of the mid-point in the array is calculated as
|
Mid := (Temp'First + Temp'Last) / 2; |
The minimum index value of an unconstrained array instance may be any valid value within the specified array index subtype. In this case the minimum value may be any number from 1 through 2^31 – 1. Temp’First evaluates to the minimum index value of the array Temp. Temp’Last evaluates to the maximum index value of the array Temp. The middle index value in the array is calculated by summing the minimum and maximum index values and dividing that sum by 2.
The Temp array in the Find_Median function is declared on the function stack. It therefore is reclaimed with the rest of the stack data when the function completes.
The function returns the value of the array indexed by the variable Mid.
A full program declaring and using the Find_Median function is:
|
with
Ada.Text_IO; use Ada.Text_IO; |
The output of this program is:
|
The median of A1 and A2 is 8.00000E+00 |
No comments:
Post a Comment