(CS50)-알고리즘 기초(삽입정렬)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 삽입 정렬
• 배열

삽입 정렬

• 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법

실행

[삽입정렬예시]

• 배열의 첫 번째 자리(5)는 이미 정렬된 부분이라고 간주.
• 정렬되지 않은 부분의 맨 앞자리 1은 5보다 작기 때문에 5는 오른쪽으로 이동하고 1이 첫 번째 자리로 옴.
• 다음으로 정렬되지 않은 부분의 6을 살펴봄.
• 6은 5보다 크기 때문에 이동할 필요 없음
• 같은 방식으로 계속 실행하면 전체 값이 모두 정렬

정리

• 어떤 원소가 정렬된 배열 내에서 자리를 잡았다고 해서 최종적인 자리라는 보장이 없다
  • 다음 단계에서 다른 자료에 의해 위치가 바뀔 수 있기 때문.
• 자료의 양이 적을 때 성능이 우수하고 자료 대부분이 이미 정렬되어 있는 경우 효율적.
• 안정성이 낮다는 단점.
  • 이미 정렬된 자료에 새로운 자료를 삽입하는 경우 정렬된 자료들이 자리를 이동해야 하므로