You have an array A[0], A[1], ..., A[n-1] of numbers (integers or floating point
ID: 3701648 • Letter: Y
Question
You have an array A[0], A[1], ..., A[n-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:
(A[0], A[1], ..., A[t-1])
(A[t], A[t+1], ..., A[2t-1])
(A[2t], A[2t+1],..., A[3t-1])
etc
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.
Write down the pseudocode for an algorithm that sorts such an array. The input to the algorithm is the array A[ ], 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.
Explanation / Answer
The sorting algorithm is as below:
SortArray(A[], n, t)
{
topA = 0;
topB = t;
while( topA <t || topB < n)
{
if (A[topA] < A[topB])
{
swap (A[topA], A[topB])
index = topB;
while (A[index] <A[index + 1]) {
swap(A[index], A[index + 1])
}
topB++
} else {
topA++;
}
}
}
This algorithm is a bubble sort mechanism. Therefore, the complexity of this algorithm will be greater than O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.