binary insertion sort

Question

I've got a question that says use the binary insertion sort in which a binary search algorithm is used to determine the index to sort a list:

So, without thinking I tried implemented this for hours:

from binsert import binsert


def binary_insertion(List,L,R):
    """uses binary searching algorithm
    to determine the position for insertion"""



    for i in range(1,len(List)):
        position = binsert(List, i, L, R)
        for k in range(0, i-position):
            #note: the position must be atleast one
            #less than j otherwise this code won't
            #run, and it gives accuracy to statement:
            List[position-k] = List[position-k-1]
            #as the list bound is never exceeded


if __name__ == '__main__':

    List = [8, 9, 16, 17, 31, 34, 35, 39, 41, 45]
    Lcopy1 = List[:]
    Lcopy2 = List[:]


    binary_insertion(Lcopy1, 0, len(List)-1)
    print("The binary is: ", Lcopy1)  

Where the binsert contains:

#!/usr/bin/python3

def binsert(List, search, L, R):
    """binary insertion determining algorithm"""
    List.sort()

    if L > R:
        #some code here

        ''' elif L == len(List):
            return L
        else R < 0:
            return L
        else:
            return L '''

        return L


    mid = (L+R)//2

    if List[mid] == search:
        return mid
    elif search < List[mid]:
        return binsert(List, search, L, mid-1)
    elif search > List[mid]:
        return binsert(List, search, mid+1, R)

if __name__ == '__main__':

    import random


    List =  [0, 9, 18, 25, 29, 34, 39, 40, 43, 49]
    print("The length of the list is: ", len(List))
    print("The list is: \n",List)
    Listnumber = binsert(List, 26, 0, len(List)-1)
    print("The item is to be inserted in: {}".format(Listnumber))  

Now after I was done with these, I realized that This is a sorting algorithm but the binary search required input to be sorted, and I was trying to implement mutually exclusive things.

Either I've done a mistake in understanding and there's another explanation to what the question was saying, Or I just wasted my time.

So, I wanted to know what was the case.

Answer 1

You're basically doing two errors.

First of all the array you do binary insertion to must be sorted before insertion, but you're working on the entire input array when you're doing the binary insertion.

The second error which might show if you correct the first is that if you're working in-place you must take care not to destroy data. When inserting into the sorted portion of the array that portion will grow by one element and extend to the elemnt that is to be inserted.

Answer 2

Thanks to the sentences of skyking, I was able to solve this:

import random



def binsert(List, search, L, R):
    """binary insertion determining algorithm"""
    if L > R:
        #some code here
        return L

    mid = (L+R)//2

    if List[mid] == search:
        return mid
    elif search < List[mid]:
        return binsert(List, search, L, mid-1)
    elif search > List[mid]:
        return binsert(List, search, mid+1, R)

# binsert defn-> binsert(List, search, L, R)

def binsertion_sort(List):
    for i in range(1, len(List)):
        L = 0 #left index
        R = i-1
        position = binsert(List, List[i], L, R)

        curvalue = List[i]
        for k in range(i-position):
            List[i-k] = List[i-k-1]

        List[position] = curvalue

if __name__ == '__main__':
    import random
    List = random.sample(list(range(1, 1000)), 10)
    Lcopy1 = List[:]
    Lcopy2 = List[:]

    print("The copy is: ",Lcopy1)    
    binsertion_sort(Lcopy1)
    print("The list is: ", Lcopy1)
    print("The rslt is: ", Lcopy1 == sorted(Lcopy2))