알고리즘 5(삽입 정렬)

안녕하세요

 

게임개발자가 되기위해 공부하고있는 구구입니다.

오늘은 알고리즘의 삽입정렬에 대해 알아보도록 하겠습니다.

---

• 삽입 정렬

- 앞의 숫자가 나보다 크닞 비교하면서 자신의 위치에 삽입하는 정렬

- 앞의 값과 비교를 하기 때문에 전체 배열 중 0번 인덱스가 아닌 1번 인덱스부터 앞의 값과 비교함.

 

 

• 삽입 정렬 특징

- 빠르진 않음.

- 비교할 데이터가 많을 때 효율이 좋지 못함

 

 

• 시간 복잡도

- O(n^2)

 

최악의 경우를 고려해보면 '역순으로 정렬된 경우' 입니다.

 

1회차 : n-1, 2회차 : n-2, ····· n-1회차 : 1

따라서 비교하는 횟수를 전부 합치면 1부터 n-1까지의 등차수열의 합이기 때문에 n의 2차식꼴이 나옵니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

오늘은 여기까지 하도록 하겠습니다.