Hi Saiteja
I understand that you want to implement Binary Insertion Sort, which is a variation of Insertion sort algorithm that uses binary search to find the appropriate index of the array elements.
Here is the code for the same:
x = [4 5 4 0 0 6 4 7 8 5 3 1];
sorted = binaryInsertionSort(x)
function index = binarySearch(inArr, len, val)
if len < 1
index = 1;
return;
end
l = 1;
r = len;
while l <= r
mid = ceil((l + r) / 2);
if inArr(mid) == val
index = mid;
return;
else
if inArr(mid) > val
r = mid - 1;
else
l = mid + 1;
end
end
end
index = l;
end
function sortedArray = binaryInsertionSort(inArray)
sortedArray = inArray;
n = length(inArray);
for i = 1:n
val = sortedArray(i); % get the current element
pos = binarySearch(sortedArray, i-1, val); % find appropriate position for the current element
sortedArray = [sortedArray(1:pos-1) val sortedArray(pos:end)]; % insert element in the appropriate position
sortedArray(i+1) = []; % remove the current element, as its already inserted once in the last line
end
end
Hope it helps
Ishaan Mehta
