[Algorithm] (이코테) 삽입 정렬 - 파이썬

교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 6 정렬
실전문제 6-2 삽입 정렬 161

삽입 정렬 기본예제

문제

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이트는 이미 정렬되어 있다고 가정하고 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입되는 삽입 정렬(Insertion Sort)를 진행하라

제시된 데이터 : 7, 5, 9, 0, 3, 1, 6, 2, 4, 8

접근

위치 하나 잡아놓고 감소하며 비교하는 걸 생각을 못했당..ㅎㅎ 그래서 while문으로 돌려놓고 앞뒤 비교하다가 참고하고 고쳤당..ㅋㅋ 어렵진 않구려

노트

 for j in range(i,0,-1):     # 인덱스 i부터 1까지 감소하며 반복하는 문법

풀이

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1,len(arr)):
    for j in range(i,0,-1): 
        if arr[j]<arr[j-1]:
            arr[j],arr[j-1]=arr[j-1],arr[j]
        else:
            break

print(arr)

삽입 정렬

• 시간 복잡도 : O(N^2)
• 최선의 경우 O(N)의 시간 복잡도
  - 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

References

이것이 코딩 테스트다 with 파이썬 - 나동빈 저