삽입 정렬

삽입 정렬

• 자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성
• o(n^2)

 

삽입 정렬의 정렬 과정

• 정렬할 자료를 두 개의 부분집합 S와 U로 가정
  • 부분집합 S : 정렬된 앞부분의 원소들
  • 부분집합 U : 아직 정렬되지 않은 나머지 원소들
• 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 (반복)
• 삽입정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소
• 부분집합 U가 공집합이 되면 삽입정렬이 완성

# 삽입 정렬
lst=list(map(int, input().split()))     # 정렬되지 않은 리스트

for i in range(1, len(lst)):      # 1부터 끝까지
  for j in range(i, 0, -1) :      # 거꾸로
    if lst[j-1] > lst[j] :      # 이전 값이 더 크면
      lst[j-1], lst[j]=lst[j], lst[j-1]     # 값 교환
print(lst)		# 오름차순으로 정렬된 결과

 

리스트 lst의 1부터 끝까지 이전 값들과 비교한다.

이전 값이 더 크면 값을 교환한다.

 

 

---

참고. SW expert academy