(Problem C-12.28, page 568 of the text) Linda claims to have an algorithm that t
ID: 648954 • Letter: #
Question
(Problem C-12.28, page 568 of the text) Linda claims to have an algorithm that takes an input sequence S and produces an output sequence T that is a sorting of the n elements in S.
a) Give an algorithm, isSorted, that tests in O(n) time if T is sorted.
b) Explain why the algorithm isSorted is not sufficient to prove a particular output T of Linda's algorithm is a sorting of S.
c) Describe what additional information Linda's algorithm could output so that her algorithm's correctness could be established on any given S and T in O(n) time.
Explanation / Answer
isSorted(T)
{
i=1
if(A[i] <A[i+1]
{
for i=2 to i =n-1
{
if(T[i] >T[[i-1])
{ break;}
}
else
{
for i=2 to n-1
{
if(T[i]<T[i+1])
{ break; }
}
}
if(i==n-1)
{
algorithm is sorted
}
else
{
algorithm is not sorted
}
b) when the sequences has repitation of numbers , then the algorithm may fail
c) add the euality sign in if statements to avoid this
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.