누구나 자료 구조와 알고리즘 | 긍정적인 시나리오 최적화 | 삽입 정렬 알고리즘

✔️ 삽입 정렬

1. 인덱스 1의 값을 변수에 담아둔다.

2. 왼쪽의 값과 변수에 담아둔 값을 비교한다.

3. 왼쪽 값이 더 크다면 오른쪽으로 쉬프트, 작다면 해당 패스스루 끝내기

4. 쉬프트하여 빈 자리에 변수로 담아둔 값을 넣는다.

5. 마지막 인덱스까지 반복

 

✔️ 삽입 정렬 코드 구현

 

✔️ 삽입 정렬의 효율성

• 원소가 N개인 배열
  • 비교 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교
  • 시프트 : 1 + 2 + 3 + … + (N-1) ⇒ 대략 N^2 / 2 번의 비교
  • 삭제 : N-1번
  • 삽입 : N-1번
  • 총 단계 수 : N^2 + 2N - 2단계
• 원소가 5개인 배열
  • 비교 : 1 + 2 + 3 + 4 = 10번
  • 시프트 : 1 + 2 + 3 + 4 = 10번
  • 삭제 : 4번
  • 삽입 : 4번
• 원소가 10개인 배열
  • 비교 : 1 + 2 + 3 + … + 9 = 45번
  • 시프트 : 1 + 2 + 3 + … + 9 = 45번
  • 삭제 : 9번
  • 삽입 : 9번
• 원소가 20개인 배열
  • 비교 : 1 + 2 + 3 + … + 19 = 190번
  • 시프트 : 1 + 2 + 3 + … + 19 = 190번
  • 삭제 : 19번
  • 삽입 : 19번
• 삽입 정렬의 총 단계 수 : N^2 + 2N - 2단계
  • 빅 오는 상수를 무시한다 ⇒ O(N^2 + N)으로 정리
    • but 다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다. ⇒ O(N^2)
      why? N이 증가할수록 가장 높은 차수의 비중이 훨씬 크기 때문이다.

 

✔️ 두 배열의 교집합 구하기 - Javascript