binary insertion sort code in matlab
3 views (last 30 days)
Show older comments
Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion. The number of swaps can be reduced by calculating the position of multiple elements before moving them. For example, if the target position of two elements is calculated before they are moved into the right position, the number of swaps can be reduced by about 25% for random data. Write a program to simulate performance of BINARY INSERTION SORT.
0 Comments
Answers (1)
Ishaan Mehta
on 26 Jun 2022
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
0 Comments
See Also
Categories
Find more on Shifting and Sorting Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!