(10 points) Many operations can be performed faster on sorted data than on unsor
ID: 3804481 • Letter: #
Question
(10 points) Many operations can be performed faster on sorted data than on unsorted data. For
each of the following operations, state whether it could be performed faster if the data values were
sorted (do not take the cost of the sorting into account). Please give a brief explanation. Assume an
array is used to store data.
(a) Find the median value.
(b) Calculate the sum of all data in the array.
(c) Partition the array according to a given pivot value.
(d) Insert a new value to the middle position (which is empty) of the array.
Explanation / Answer
a) median value:
To find the median, operation on the sorted array is faster as we will have the length of the array directly and all the elements are sorted.
So we can easily calculated by finding the middle element.
b)Sum of all data in the array:
Performance is same for both sorted and unsorted array in thi case. For calculating the sum of all data we end up with adding all the elements in
the array from index(0...n-1). So there is not concept of sort in this case.
c)Partition the array according to a given pivot value.
Partitioning an array based on pivot is faster on sorted arrays. As in a array if a pivot is given, all the elements to the left of the pivot mucst be
less than the pivot and all the elements to the right of the pivot must be greater than the pivot.
d)Insert a new value to the middle position (which is empty) of the array.
Inserting a new value to the middle postion is same in both sorted and unsorted arrays. As middle position in the sense n/2 index, we can directly insert
data at that position.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.