binary insertion sort code in matlab

Question

saiteja gundabathula 2015-4-19

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/210295-binary-insertion-sort-code-in-matlab

回答： Ishaan Mehta 2022-6-26

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Ishaan Mehta 2022-6-26

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/210295-binary-insertion-sort-code-in-matlab#answer_994015

在 MATLAB Online 中打开

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)
sorted = 1×12
     0     0     1     3     4     4     4     5     5     6     7     8
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