본문으로 건너뛰기
실습하기

삽입 정렬 자세히 알아보기

1. 반복문 설정​

배열의 각 요소에 대해 반복합니다. 첫 번째 요소는 이미 정렬된 것으로 가정합니다.

반복문 설정
for i in range(1, len(arr)):

2. 현재 요소 선택 및 적절한 위치 탐색​

현재 요소를 선택하고, 이전 요소들과 비교하여 적절한 위치를 찾습니다.

현재 요소 선택 및 적절한 위치 탐색
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
    arr[j + 1] = arr[j]
    j -= 1
arr[j + 1] = key

시간 복잡도​

  1. 최악의 경우 시간 복잡도: O(n^2)

    • 최악의 경우는 입력 배열이 역순으로 정렬되어 있을 때 발생합니다. 이 경우, 각 새 요소를 삽입할 때마다 이미 정렬된 배열 부분의 모든 이전 요소들과 비교해야 하므로, n개의 요소에 대해 대략 (nxn)번의 비교가 필요합니다.

  2. 최선의 경우 시간 복잡도: O(n)

    • 배열이 이미 정렬되어 있는 경우입니다. 새로운 요소를 삽입할 때마다, 이미 정렬된 부분에서 적절한 위치를 바로 찾을 수 있으므로, 각 요소에 대해 한 번씩만 비교하면 됩니다. 따라서, 배열의 크기만큼, 즉 n번의 비교가 필요합니다.

  3. 평균 시간 복잡도: O(n^2)

    • 일반적인 경우, 즉 배열의 요소들이 무작위로 배치되어 있을 때는 평균적으로 n^2 비례하는 비교가 필요합니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!