Insertion sort - Python

Question

I am trying to implement insertion sort using the min() function on python. It works for most of the cases however when I plug in the value of 0 more than once the entire thing breaks down. The code is as following :

def sortArray(self, nums: List[int]) -> List[int]:
        # Selection sort 
        for i in range(len(nums)):
            temp = nums[i]
            index = nums.index((min(nums[i:])))
            print(f"val = {nums[index]} nums[{i}:]")
            nums[i] = min(nums[i:])
            nums[index] = temp
            print(f"Step : {i} -- {nums}")
        return nums

For a test case [-100, 0, 0, -1, -4, 0, 200, 30, 4000, 32, -19] I receive following output:

val = -100 nums[0:]
Step : 0 -- [-100, 0, 0, -1, -4, 0, 200, 30, 4000, 32, -19]
val = -19 nums[1:]
Step : 1 -- [-100, -19, 0, -1, -4, 0, 200, 30, 4000, 32, 0]
val = -4 nums[2:]
Step : 2 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = -1 nums[3:]
Step : 3 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[4:]
Step : 4 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[5:]
Step : 5 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[6:]
Step : 6 -- [-100, -19, -4, -1, 200, 0, 0, 30, 4000, 32, 0]
val = 0 nums[7:]
Step : 7 -- [-100, -19, -4, -1, 200, 30, 0, 0, 4000, 32, 0]
val = 0 nums[8:]
Step : 8 -- [-100, -19, -4, -1, 200, 30, 4000, 0, 0, 32, 0]
val = 0 nums[9:]
Step : 9 -- [-100, -19, -4, -1, 200, 30, 4000, 32, 0, 0, 0]
val = 0 nums[10:]
Step : 10 -- [-100, -19, -4, -1, 200, 30, 4000, 32, 0, 0, 0]

Amin Gheibi · Accepted Answer · 2021-02-08 19:26:30Z

1

The issue is you have duplicated zeros. At index six the min is 0. When you lookup the value zero in the entire array it picks the first zero and replace it with 200. This is the edit that makes your code to work:

def sortArray(self, nums) -> list[int]:
        # Insertion sort 
        for i in range(len(nums)):
            temp = nums[i]
            index = nums[i:].index((min(nums[i:])))
            print(f"val = {nums[i+index]} nums[{i}:]")
            nums[i] = min(nums[i:])
            nums[i+index] = temp
            print(f"Step : {i} -- {nums}")
        return nums

This is the output:

val = -100 nums[0:]
Step : 0 -- [-100, 0, 0, -1, -4, 0, 200, 30, 4000, 32, -19]
val = -19 nums[1:]
Step : 1 -- [-100, -19, 0, -1, -4, 0, 200, 30, 4000, 32, 0]
val = -4 nums[2:]
Step : 2 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = -1 nums[3:]
Step : 3 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[4:]
Step : 4 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[5:]
Step : 5 -- [-100, -19, -4, -1, 0, 0, 200, 30, 4000, 32, 0]
val = 0 nums[6:]
Step : 6 -- [-100, -19, -4, -1, 0, 0, 0, 30, 4000, 32, 200]
val = 30 nums[7:]
Step : 7 -- [-100, -19, -4, -1, 0, 0, 0, 30, 4000, 32, 200]
val = 32 nums[8:]
Step : 8 -- [-100, -19, -4, -1, 0, 0, 0, 30, 32, 4000, 200]
val = 200 nums[9:]
Step : 9 -- [-100, -19, -4, -1, 0, 0, 0, 30, 32, 200, 4000]
val = 4000 nums[10:]
Step : 10 -- [-100, -19, -4, -1, 0, 0, 0, 30, 32, 200, 4000]

edited Feb 8, 2021 at 19:26

answered Feb 8, 2021 at 19:13

Amin Gheibi

7881 gold badge10 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Karun Dawadi Over a year ago

Thank you for the explanation. I am very new with programming. How did adding i solve the issue?

Amin Gheibi Over a year ago

I have changed this line index = nums.index((min(nums[i:]))) to index = nums[i:].index((min(nums[i:]))) in order to search only in the portion of nums that have not been seen before. Then index is valid in nums[i:]. In order to swap values in nums array we need to add i to index

Collectives™ on Stack Overflow

Insertion sort - Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related