[백준 2750] 파이썬 삽입정렬

이미지 출처 : 위키피디아 삽입정렬

 

삽입정렬은 리스트의 2번째요소에서 시작해서 앞의 요소들과 비교해서 위치를 찾아가는것이다

코드 구현이 쉽고 데이터크기가 작은경우 복잡하게 구현된 코드들보다 빠를수있으나

코드가 커질수록 비효율적이고 최악의경우 N^2 의 시간복잡도를가짐

 

파이썬코드

import sys
list=[]
N = int(sys.stdin.readline())

for i in range(0,N):
    list.append(int(sys.stdin.readline()))

for i in range(1,N):
    for j in range(i,0,-1):
        if list[j] < list[j-1]:
            list[j], list[j-1] = list[j-1], list[j]
        else:
            break
for i in list:
    print(i)