문제

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)
도움이 되었습니까?

해결책

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)
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top