-2

I have the following homework question: You develop a video surveillance software that must run on real-time data. In one of the steps of the algorithm executed with each image captured by the camera, you have to sort some numbers. Considering that the average execution time of QuickSort is better than that of MergeSort, which Sorting should you consider using? justify

I know that QuickSort isn't good with larger dataset as opposed to MergeSort. I also think that because we are working with data that continuously updates speed is incredibly important. But considering that its real-time that means that the size of the data set is small initialy and then grows.

It seems like a trap to go for QuickSort because the question is heavily promoting it. On the other hand MergeSort is more stable it always have a complexity of O(n log n). I don't know which to choose and how to justify it properly.

Improve this question
  • 1
    I'd use the Bad Question Sort. There are at least a half-dozen variables that would favor one or the other. The question only mentions one and not even explicitly as a requirement. If your prof is trying to teach you how to reason about how you develop your software, he's doing a terrible job of it. – Blrfl Apr 6 '19 at 23:20
  • 3
    @Blrfl Strange thing to say, when the Prof is obviously trying to get the student to think about the properties of both and in what conditions either is better - and what conditions might apply here. In particular I presume the lesson is that average faster isn't always what you aim for, as that is the default many students would rank such algorithms by. – Frank Hopkins Apr 6 '19 at 23:31
  • Relevant:pdfs.semanticscholar.org/0f8f/… – NoChance Apr 7 '19 at 9:23
  • 1
    @FrankHopkins The question invites a comparison between the sorts, but that comparison raises more questions than it answers. OP was forced to make some assumptions in the second paragraph that could turn out to be wrong (e.g., maybe the set of numbers isn't growing and is instead some figure calculated from the last five frames), invalidating the justification. The only valid answers to the question as written would be "consider both until the other properties of the data are known" and "if average speed is the only criterion, the question answers itself." – Blrfl Apr 7 '19 at 11:17
  • 1
    @FrankHopkins We're going to have to disagree on this one, and I'm good with that. I would be interested to hear how the assignment went for the OP along with any after-the-fact discussion that happened in class. – Blrfl Apr 7 '19 at 16:33
4

Likely there isn't necessarily a single correct answer, but your professor wants to see how well you know the properties of both algorithms and whether you can justify a set of constraints / goals in the given setting that make you prefer one (for good reasons).

That said, the hint that it's real-time processing strongly suggests one line of reasoning that you already seem to have come up with half-way.

Improve this answer
0

The point here is that average performance is not relevant in this case. You want an algorithm that, in a worst case scenario, will still fit in the time slot you have been granted. That time slot is one frame period. When you are done processing you have to wait for the next frame anyway. Then it is better to need 90% of the slot in a worst case scenario that occurs often then to do it in 25% of the slot for 99% of the cases but to fall short in the remaining 1%.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.