[정렬 알고리즘] 예제2 - 삽입 정렬(Insertion Sort)(164p)

[이코테] 예제2 - 삽입 정렬(Insertion Sort)(164p)

풀이 시간: 

 

1) 문제 해결 아이디어

<삽입 정렬>

정렬된 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입

(첫번째 데이터는 정렬되어있다고 가정, 2번째 데이터부터 정렬 시작)

평균 시간 복잡도: O(n**2)
공간 복잡도: O(n)

 

2) 소스코드

# 선택 정렬(Insertion Sort)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 오름차순 정렬
# 1번 인덱스부터 시작
for i in range(1, len(array)):
  # 0 ~ i 인덱스 정렬
  for j in range(i, 0, -1):
    # 현재값이 왼쪽값보다 크면 탈출
    if array[j] > array[j - 1]:  break
    # 현재값이 왼쪽값보다 작다면 swap
    else:
      # swap (현재값 & 왼쪽값 서로 바꾸기)
      array[j], array[j - 1] = array[j - 1], array[j]

print(array)