Insertion Sort

صورت مسأله: مرتب سازی الحاقی نوعی الگوریتم مرتب سازی با پیچیدگی زمانی (O(n^2 هست که برای مجموعه کوچک اعداد به خوبی جواب میده. روش کار به این صورت هست که کامپیوتر از اولین عدد شروع میکنه و اگر عددی بزرگتر قبل از اون عدد وجود داشته باشه، اون عدد رو قبل از عدد بزرگتر قرار میده و این کار رو تا آخرین عدد تکرار میکنه. به صورت زیر:

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

t اندازه مجموعه و melt مجموعه عددی دریافت شده به صورت string که به یک لیست تبدیل شده است

مثال:

ورودی

8
8 3 2 6 5 6 9 1

 

خروجی:

3 8 2 6 5 6 9 1
2 3 8 6 5 6 9 1
2 3 6 8 5 6 9 1
2 3 5 6 8 6 9 1
2 3 5 6 6 8 9 1
2 3 5 6 6 8 9 1
1 2 3 5 6 6 8 9

راه حل:

---

t = input()
melt = [int(x) for x in raw_input().split()]
i = 0
for z in melt :
    c = i
    while c > 0 and i <= len(melt) - 1 and melt[c] < melt[c-1] :
        melt.insert(c-1, melt.pop(c))
        c -= 1
    if i != 0 :
        print " ".join([str(b) for b in melt])
    i += 1