You are viewing our Forum Archives. To view or take place in current topics click here.

Binary Search Algorithm comparisons for sorted array? +repPosted:

Gavin-
  • Ninja
Status: Online
Joined: Nov 02, 20134 Year Member
Posts: 4,288
Reputation Power: 820
So this question has me confused i know how many comparisons there are for and unsorted array but the questions says

The efficiency of the InsertionSort algorithm is ~n2/4 in terms of time complexity.
Insertion sort has a desirable property - if the array is already sorted, its performance is
much better than this.


Using this array

15, 18, 20, 21

give the num of comparisons required.
#2. Posted:
Cyimking
  • V5 Launch
Status: Offline
Joined: May 02, 20126 Year Member
Posts: 1,111
Reputation Power: 33
Sounds like it's asking you to use the insertion sort algorithm and binary search algorithm on this array. Then compare how long it took to complete it. but the question is unclear.
#3. Posted:
Xaldin
  • 2 Million
Status: Offline
Joined: Oct 09, 20107 Year Member
Posts: 2,277
Reputation Power: 102
3
compares 15 and 18 - sees that its ok
compares18 and 20 - sees that its ok
compares 20 and 21 - sees that its ok
zero swaps so Done
#4. Posted:
-Deano
  • Rated Awesome
Status: Offline
Joined: Aug 19, 20107 Year Member
Posts: 4,948
Reputation Power: 429
As Xaldin said, as well as in the question, if the array is already sorted, the number of comparisons would simply be ( n - 1 ).

This means that it is incredibly fast at working with already sorted data (or mostly sorted data) which is why it would mostly be used at inserting a new value in already sorted arrays.
Jump to:
You are viewing our Forum Archives. To view or take place in current topics click here.