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-
  • Blind Luck
Status: Offline
Joined: Nov 02, 20134 Year Member
Posts: 4,319
Reputation Power: 1810
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
  • 2 Million
Status: Offline
Joined: May 02, 20126 Year Member
Posts: 1,119
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
  • 1K Rainmaker
Status: Offline
Joined: Oct 09, 20108 Year Member
Posts: 2,321
Reputation Power: 104
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, 20108 Year Member
Posts: 4,979
Reputation Power: 433
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.