Investigation on How Many Comparisons Pigeonhole Sort Takes.

Answer to C: Investigation on how many comparisons pigeonhole sort takes.
I. The following table showing how many comparisons (comparisons of type A) between list
items would be needed to find the largest number in lists of different lengths.
Length of unsorted_list 10 20 30 40
Number of comparisons between list items needed to
find largest number in unsorted_list
9 19 29 39
Above table indicate that the relationship between the length of the unsorted_list and the
number of comparisons between list items needed to find largest number in unsorted_list is
linear. It is linear because algorithm has no idea of position of largest number. Let’s suppose
that largest number is at first place but algorithm can declare it largest only after comparing
all the number until the last one (it may happen that largest number is at last position). If list
has only one number then there is no need of comparison for finding largest number. If list
has two numbers then there will be only one comparison for finding largest number. If list
has three numbers then there will be two comparisons for finding largest number. Hence, if
list has n numbers then there will be n-1 comparisons for finding largest number. So, the
number of comparisons needed is linear
II. The following table showing how many comparisons (comparisons of type B) are needed between
items in the pigeonholes list and the empty string, for different largest numbers.
Largest number in unsorted_list 10 20 30 40
Number of comparisons needed between items
in pigeonholes list and empty string.
10 20 30 40
Above table indicate that the relationship between the largest number in the unsorted_list
and the number of comparisons needed between items in pigeonholes list and empty string
is linear. It is linear because algorithm needs to check each pigeonhole and compare with
empty string to copy number back to original list. And the size of pigeonhole list is same as
largest number in unsorted_list. So, the number of comparisons needed between items
in pigeonholes list and empty string is linear.

Answer to D: The performance comparison of pigeonhole sort with the
selection sort.
I. Suppose, a list of 50 numbers of which the largest was 100 then 1225 comparisons would
be needed to sort them using selection sort. According to n x (n – 1) / 2, where n is size of
unsorted list, number of comparison requires to sort the numbers in list using selection sort
is 50 x (50 – 1) / 2 = 50 x (49) / 2 = 2450 / 2 = 1225. And it has no relation with largest
number in unsorted list. Now for the number of comparison needed to sort the list using
pigeonhole sort, we need to calculate both types of comparison (type A and type B). Type A
comparisons: It is linearly equals to n-1, which is number of items in the list less one. So it is
50-1=49.Type B comparisons: It is linearly equals to largest number, which is size of
pigeonhole list. So it is 100. So total number of comparison needed to sort the list using
pigeonhole sort is 49 + 100 = 149.
II. In above situation, pigeonhole sort is much more efficient than selection sort. But it will
not be always true. Because number of total comparison needed to sort list using
pigeonhole sort is dependent on both size of list and largest number in the list and total
number of comparison needed to sort list using selection sort is dependent on only size of
list. Let’s have largest number in above situation is 1000000. Then type B comparisons
needed are 1000000. Hence the total number of comparison needed is 1000000 + 49 =
1000049. In this situation pigeonhole sort is much less efficient than selection sort.
III. Disadvantage unrelated to the number of comparisons involved in pigeonhole sort is
Space complexity; it requires extra space (pigeonhole list) other than original array and its
size equals to largest number in the list.