How to do Python insertion sort on certain range of the list only?

user_15430402 0
Viewed 62

So, I tried and get [1, 2, 3, 5, -4] but I want to get [3, 1, 2, 5, -4] as result instead; because I want to sort only from index 1 to index 4 (including start, excluding end; which mean only sorting from index 1 to index 3, leaving index 0 and 4 as it is) of the list

def insertionSort(the_list, start, end):
    for mark in range(start, end):
        temp = the_list[mark]
        i = mark-1
        while i >= 0 and the_list[i] > temp:
            the_list[i+1] = the_list[i]
            i -= 1
        the_list[i+1] = temp

    return the_list

print(insertionSort([3, 2, 5, 1, -4], 1, 4))

Can someone help me fix the code so I can get the result I want? Thank you.

insertion-sort python
1 Answers

You need to slice the section you want to sort. Here's how I would implement.

def insertionSort(alist,s, e):

    #check if s or e is greater than the length of the list
    if s >= len(alist) or e >= len(alist):
        #if True, then request is invalid
        return ('invalid request')

    #sort the list for the slice of data
    alist[s:e] = sorted(alist[s:e])

    # now return the full list 
    # The above code ensures you are not touching values before and after
    return alist

print (insertionSort([3, 2, 5, 1, -4], 1, 4))

The output of this will be:

[3, 1, 2, 5, -4]

Explanation of issues in your code:

Your for loop starts from start to end. However, you are checking for values from start - 1 (code i = mark - 1). When mark is 1 (start), you are setting i to 0 (mark - 1 i.e., 1 - 1 = 0). That makes your code consider 0th position. That's why you are getting 1, 2, 3, 5, -4 as the output.

Also, if you give a value greater than the number of elements in the list, your code will crash. You have to take care of that condition as well. For example, if you give print (insertionSort([3, 2, 5, 1, -4], 1, 7)), the code will crash.

user_138739800
Related