Describe the sort pattern. Discuss the quick sort routines in terms of this pattern.
What will be an ideal response?
Sort array
1)Get split point and Split two parts
2)Sort first part(recursive)
3)Sort second part (recursive)
4)Join sorted parts.
Quick sort:
1)Split into what we hope are roughly equal parts,
this may not be the case.
Postcondition on the split: Each element in upper
half is >= each element in the lower half. The hard
work is done here.
2)Recursively sort the first part
3)Recursively sort the second part
4)The join is trivial
The division into two pieces of nearly equal size will cause the routine to run in N log N time, that is, O(N log N) time. There is a non-negligible probability that the arrays will consistently be of size 1 and size N-1 respectively, which will result in O(N2) run time
You might also like to view...
Explain how to select an image (not the frame) with the Selection tool.
What will be an ideal response?
After a bibliography is prepared, it is not possible to update it with additional sources
Indicate whether the statement is true or false
The Random menu can be used to build stories that behave differently each time they are performed.
Answer the following statement true (T) or false (F)
In a CASE statement that uses a simple when clause, what follows CASE?
a. Value expression b. Search condition c. WHEN d. ELSE