C Programming Challenge #08: Sort - insertion (binary search variant)

Insertion sort explained in C Programming Challenge #02: 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