Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only.

a) Heapsort b) Quicksort c) MergeSort d) Insertion Sort.

I'm looking for difference in number of comparison required for sorting the list.

Exact Question: How the restriction of 0's and 1's element may affect the total number of comparison done and give the resulting \theta bound. In my perspective there won't be any change in MergeSort and Insertion sort as they would require the same number of comparison.

However on a very different thought, I'm thinking that if we know about the data (i.e. they are 0 or 1) then in decision tree there won't be n! factorial outputs. As we can reduce it to few less I'm not sure about this decision tree thought. Please provide your thoughts on this.

share|improve this question
3  
Side note: Counting sort would sort such an array in $O(n)$. en.wikipedia.org/wiki/Counting_sort –  Ayman Hourieh Sep 27 '12 at 0:35
    
Have you considered asking this on the computerScience.SE beta site? –  Rick Decker Sep 27 '12 at 18:47
    
Nopes, I'm not aware of this website. Can you give me exact url? (computerScience.se doesn't load) –  Rohit Kandhal Sep 27 '12 at 18:54
add comment

2 Answers 2

up vote 1 down vote accepted

Mergesort is an oblivious algorithm, which is to say that it will perform the same steps (except for those involved in merging) for each input sequence, so its average-and worst-case times will be $\Theta(n\log n)$ on inputs restricted to $0/1$ sequences.

Insertion sort becomes interesting for your inputs, but it's not too hard to see that the worst-case running time will still be $O(n^2)$: Look at the number of swaps that will have to be done on the input $\langle\; 1, 0, 1, 0, \dots , 1, 0\;\rangle$. The average performance is, as usual, more involved and I'm not ready to claim any results for that.

Quicksort is even more interesting, since the first call to partition will leave the array in sorted order after $O(n)$ swaps. If QS were written with that in mind, then its behavior would change from $O(n\log n)$ on average (or $O(n^2)$ in the worst case) to $O(n)$. If this fact weren't identified, then after the first partition, the subsequent ones would split each subarray into two pieces, one containing a single element and the other containing all the rest, leading to $O(n^2)$ performance in both average- and worst-case.

Oops! I just noticed that heapsort was also on your list. I'll have to get back to you on that.

share|improve this answer
    
Thanks for your response. :) I too got somewhat similar result but wasn't sure whether they are correct or not. Here are my results: Insertion Sort: theta(n^2), If either no. of 1's or 0's are constant then it is theta(n) Merge Sort: theta(nlogn), No change even if 1's or 0's are constant. Heapsort: theta(nlogn), If no. of 1's are constant then theta(nlogn). If no. of 0's are constant then theta(n). QUickSort: theta(n^2), No change if no. of 0's or 1's are constant. –  Rohit Kandhal Sep 27 '12 at 18:51
add comment

Best case = data already sorted Average case= some data sorted, some data unsorted. Worst case= data totally unsorted

Merge sort: Best = NlogN , AVE=NlogN, WORST = NlogN

Insertion Sort = Best = N , AVE=N^2, WORST = N^2

Quicksort = NlogN , AVE=NlogN, WORST = N^2

share|improve this answer
1  
I know about these formulas, I want to know what difference would it make with the input values between 0 and 1 only. Would there be any change theta bound of these algo? I think there will be some but I'm not able to figure out the appropriate way to findout the same. –  Rohit Kandhal Sep 27 '12 at 5:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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