3

I was preparing for a competition and came across this question, which I can't comprehend. Consider a set of 'n' elements in an array, which is sorted except for one element that appears out of order. which of the following sort sequence takes O(n) time?

  • Quick Sort
  • Heap Sort
  • Merge Sort
  • Bubble Sort

Now I already know the best method would be to use Insertion sort which would take O(n) time in this case but since its telling other than that, I'm not sure which to use.

  • Quick sort will be real bad since the array is already sorted.
  • Heap sort will not exactly utilize the property that the array is sorted and will take O(nlogn) time.
  • Merge sort also takes O(nlogn) as it doesn't discriminate the input ordering.
  • Bubble sort would also take O(n^2). Would really like some help here , Am I missing something?
4
  • You're going to have to analyze the algorithms a bit deeper than the cursory summary you've provided here. Oct 2, 2014 at 19:15
  • 1
    If you use a modified BubbleSort that runs only 2 iterations, one from the left, and one from the right, it will take O(n) time.
    – AndyG
    Oct 2, 2014 at 19:16
  • Quick sort is only O(n^2) on sorted arrays if you always pick the first or last item as a pivot. If you pick the middle item (or a random item) it's O(n log n).
    – hunse
    Oct 2, 2014 at 19:17
  • @MarkRansom : Well I was taking into consideration only the part that fits in my question in the algorithm. Do you think we can modify heap sort to make it a little better? Oct 2, 2014 at 19:25

3 Answers 3

5

The natural variant of merge sort will sort the described list in O(n) time.

It works the same as merge sort but begins by identifying natural runs in the data. So it will identify the two runs (sorted groups) around the unsorted element, then merge the unsorted element into one of the runs, then merge the two runs together. This only requires two O(n) merges (plus some O(n) run detection), no matter the size of the data, so it's O(n).

1
  • This looks good. And one more thing do you think we could use QuickSort with one run with the element out of place as the pivot? Oct 2, 2014 at 19:33
1

Insertion sort would still take O(n^2) because it won't check that the array is sorted. The best solution would be bubble sort as it would scan the array twice: the first time it would move the element to its correct place and the second time it would realize the array is sorted. keeps track of the number of swaps it makes at every iteration.

Unfortunately it is not as simple as this; it depends on the location of the unsorted item with respect to its correct place. The solution provided by AndyG would make it O(n) in all cases.

2
  • 4
    Depends on if the element starts before or after its final destination. Oct 2, 2014 at 19:16
  • Not true. Consider the case of 1,2,3,4,5,6,7,8,9,0 if the bubble sort is left->right, it will take O(n^2) time. See my comment on the OP about a modified Bubble Sort.
    – AndyG
    Oct 2, 2014 at 19:18
1

If there is exactly one element out of order, you could find it and then insert it at the correct place -> O(n) effort.

2
  • exactly. Why do one need to use sorting. Just compare consecutive elements linearly till you find a violation.
    – arunmoezhi
    Oct 2, 2014 at 19:28
  • 6
    Well, the point of the question is (as I underfstood it): which one of the listed standard sorting algorithms will do exactly that? Oct 2, 2014 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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