Question

I am heading towards sorting algorithms. I have just started to learn the Insertion Sort. I needed to make a solution for a already sorted list with an unsorted number at the end. So the problem now is that the loop skips one iteration or adds another duplicate one. Here is what I mean:

When I try to sort this list: {2, 4, 6, 8 ,3} I get this:

2 4 6 8 3
2 4 6 8 8
2 4 6 6 8
2 4 4 6 8
2 3 4 6 8
2 3 4 6 8 #duplicated! ^

And when I try to sort this list: {2, 4, 6, 8, 1} I get this:

2 4 6 8 8
2 4 6 6 8
2 4 4 6 8
2 2 4 6 8
1 2 4 6 8 #no duplicates

How can I know how many iteration do I need to complete the sort? Here's how I sort:

ar = list(map(int, input().split()))
mins = ar[-1]
for i in range(len(ar)-1, 0, -1):
    if ar[i-1] > mins: ar[i] = ar[i-1]
    else: ar[i] = mins
    print(*ar)
if mins < ar[0]: ar[0] = mins
print(*ar)
Was it helpful?

Solution

Simply break the loop when you find a[i-1] <= mins.

ar = [2, 4, 6, 8 ,1]
mins = ar[-1]
for i in range(len(ar)-1, 0, -1):
    if ar[i-1] > mins: 
        ar[i] = ar[i-1]
    else: 
        ar[i] = mins
        break
    print(ar)
if mins < ar[0]: ar[0] = mins
print(ar)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top