You are viewing our Forum Archives. To view or take place in current topics click here.
Binary Search Algorithm comparisons for sorted array? +rep
Posted:
Binary Search Algorithm comparisons for sorted array? +repPosted:
Status: Offline
Joined: Nov 02, 201310Year Member
Posts: 4,340
Reputation Power: 1865
Status: Offline
Joined: Nov 02, 201310Year Member
Posts: 4,340
Reputation Power: 1865
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.
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:
Status: Offline
Joined: May 02, 201211Year Member
Posts: 1,129
Reputation Power: 34
Status: Offline
Joined: May 02, 201211Year Member
Posts: 1,129
Reputation Power: 34
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.
- 0useful
- 1not useful
#3. Posted:
Status: Offline
Joined: Oct 09, 201013Year Member
Posts: 2,358
Reputation Power: 106
Status: Offline
Joined: Oct 09, 201013Year Member
Posts: 2,358
Reputation Power: 106
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
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
- 1useful
- 1not useful
#4. Posted:
Status: Offline
Joined: Aug 19, 201013Year Member
Posts: 5,238
Reputation Power: 532
Status: Offline
Joined: Aug 19, 201013Year Member
Posts: 5,238
Reputation Power: 532
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.
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.
- 0useful
- 0not useful
You are viewing our Forum Archives. To view or take place in current topics click here.