Question

please I need it urgent thanks algorithms

2.1 Searching and Sorting- 5 points each 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Give pseudocode for an algorithm that will solve the following problem. Given an array AlL..n) that contains every number between 1 and n +1 in sorted order, except that one of the numbers is missing. Find the missing number. Your algorithm should run in time (log n). (Hint: Modify Binary search). A pseudocode means an algorithm with if statements and loops, etc. Don't just write a paragraph. Also, if your algorithm is unclear, please explain what it does.

Answer 1

3)
The worst case complexity of quicksort is O(n^2)
these following cases will lead to worst case
i) Array is already sorted in same order.
ii) Array is already sorted in reverse order.
ii) All elements are same
in all the above cases, the pivot will divide the list unevenly which leads to worst complexity
to avoid these cases, we have to check all these cases before sorting, which can be done in O(n) times
thus it runs faster
4)
int ModifiedbinarySearch(const int array[], int numElems)

{

int first = 0, // First array element

last = numElems - 1, // Last array element

middle, // Midpoint of search

bool found = false; // Flag

while (!found && first <= last)

{

middle = (first + last) / 2; // Calculate midpoint

if (array[middle] == middle+1) // If index value and array value is matched then we have to move forward

{
first = middle + 1; //

}

else if (array[middle] > middle+1) //if index value and array value are not matched

last = middle - 1;

}

return last+1;

}