Problem 2. For this problem, you have an array Alol, A11], , Aln-1] of numbers (

Question

Problem 2. For this problem, you have an array Alol, A11], , Aln-1] of numbers (integers or floating point) to be sorted, where n is the length of the array. The array has already been partially pre-sorted in the following way: every t consecutive elements are already sorted, i.e., the following subarrays are sorted: (AIO,A1],, Alt-1) . (A[t], Alt+1], , A[2t-1]) etc The following is an example of array of values assuming t = 4: 3, 7, 13, 15, 0, 4,9, 11, 5, 6, 10, 14,1, 2, 8, 12 Assume that t divides n; and that t is known, i.e., it's an input parameter. Also assume that t may grow with n, e.g., t may be approximately log n or the square root of n. (a) 10 pt] Write down the pseudocode for an algorithm that sorts such an array. The input to the algorithm is the array AL], the length n, and parameter t. Analyze its running time and explain your analysis. For full credit, its time complexity must be the best asymptotic running time possible (Hint: Modify a sorting algorithm that you already know.)

Explanation / Answer

Note: It is similar to Merger Sort. If you use it, we will get the solution
1. read the input array a[], length n, parameter t from the console.
2. identify the number of partitions p=n/t;
3. copy the first partition to the Left Array
for (int i=0; i<p*t; ++i)
L[i] = arr[i];
4. copy the second partition to the right array
for (int j=P*t; j<(p+1)*t; ++j)
R[j] = arr[j];
5. compare the each element in Left and right array and sort them accrodingly in input array
int i = 0, j = 0;

// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
6. repeat setp3 to 5 for p-1 times.

Time complexity for the algorithm is nlogn

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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