Brian Risk The basic algorithm is this: Select an arbitrary element and add it to our sorted list, S. Select another arbirtrary element, x, and, using binary search, try to find x in S. Place x in S according to the results of the binary search. Repeat steps 2 and 3 until there are no more elements to select. Example: We shall show how to stick the number 70 into the already sorted list of {4,6,7,19,63,78,84} using binary search. The following table shows the number of comparisons (worst case) to add an element to S based on the cardinality of S. This will help us get a general feel for the cost of the algorithm. |S| So, to sort 16 elements would require 49 comparisons. It is obvious that when n, the size of the set to sort is 2k, where k is an element of the natural numbers, then total comparisons is given by the following summation: We have that when k is 1 to 5 the worst case total comparisons required to sort are 1,5, 17, 49, and 129, respectively. When examining these values,
Read full article from Binary Sort
No comments:
Post a Comment