삽입 정렬

왼쪽에 정렬된 부분을 만들고 값을 하나씩 더해 갑니다. 새 값을 꺼내서 더 작은 값을 만날 때까지 왼쪽으로 옮깁니다.

• 최선 Ω(n)
• 평균 Θ(n²)
• 최악 O(n²)
• 메모리 O(1)
• 안정
• 추가 메모리 없음

용어 설명

• 최선: 이 알고리즘에 가장 쉬운 입력일 때, 리스트 크기 n에 따라 시간이 늘어나는 정도.
• 평균: n에 따라 시간이 늘어나는 보통의 정도. n²이면 값의 개수가 두 배일 때 시간은 약 네 배이고, n log n은 훨씬 천천히 늘어납니다.
• 최악: 가장 어려운 입력에서 늘어나는 정도. 속도가 절대 떨어지면 안 될 때 중요합니다.
• 메모리: 리스트 외에 필요한 추가 메모리 양. 1은 변수 몇 개, n은 리스트 복사본 하나를 뜻합니다.
• 안정: 같은 값 두 개가 원래 순서를 유지합니다. 레코드의 한 필드로 정렬할 때 중요합니다.
• 추가 메모리 없음: 두 번째 리스트 없이 리스트 안에서 바로 정렬합니다.