**Sort - insertion**uses used linear (backward) search through the sorted sub array.

**Challenge**

**is to replace it with binary search**.

Binary search is always better than linear search in terms of performance. We cannot not directly use the binary search mentioned in C Programming Challenge #07:

**Search - binary**. We are not searching so as t say, we are trying to find the approximate position where the insertion needs to be done. Hence it would need modification.

Here are the changes only

int sort_insert(int *arr, int max) { int idx, right_card, s_idx; int ins; for(idx = 1; idx < max; idx++) { ins = search_binary_pos(arr, 0, idx, arr[idx]); right_card = arr[idx]; for(s_idx = idx - 1; s_idx >= ins; s_idx--){ arr[s_idx + 1] = arr[s_idx]; } arr[ins] = right_card; } return 0; } int search_binary_pos(int *arr, int min, int max, int key) { int start, middle, end; start = min; end = max; middle = (start + end) / 2; do { if(key > arr[middle]) { start = middle + 1; } else if (key < arr[middle]) { end = middle; } else { break; } middle = (start + end) / 2; }while (start < end); return middle; }

If you are thinking of more efficiency you can remove the function overhead of binary search position function can be in-lined.

Explanation

- Just like before outer for loop goes through all the cards from 1 till end.
- search_binary_pos is modified search_binary function and it takes both start and end index.
- Note the function call search_binary_pos(arr, 0, idx, arr[idx]), here it is finding pos between 0 to idx. Only 0 to idx -1 is sorted and item at idx has to inserted. Still this will not effect the binary search.
- Note inside search_binary_pos when key < arr[middle] we are returning end as middle, this is done to get position for insertion.

## Links

Next Article - C Programming Challenge #09: Counting in two interval

Previous Article - C Programming Challenge #07: Search - binary

All Article - C Programming Challenge

## No comments :

## Post a Comment