DAA-삽입 정렬

삽입 정렬은 오름차순 또는 내림차순으로 숫자를 정렬하는 매우 간단한 방법입니다. 이 방법은 증분 방법을 따릅니다. 게임을 할 때 카드를 정렬하는 기술과 비교할 수 있습니다.

정렬해야하는 숫자는 다음과 같이 알려져 있습니다. keys. 다음은 삽입 정렬 방법의 알고리즘입니다.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

분석

이 알고리즘의 실행 시간은 주어진 입력에 따라 크게 달라집니다.

주어진 숫자가 정렬되면이 알고리즘은 O(n)시각. 주어진 숫자가 역순이면 알고리즘은 다음에서 실행됩니다.O(n²) 시각.

예

Unsorted list:

2 13 5 18 14

1^st iteration:

키 = a [2] = 13

a [1] = 2 <13

스왑, 스왑 없음

2 13 5 18 14

2^nd iteration:

키 = a [3] = 5

a [2] = 13> 5

5 및 13 스왑

2 5 13 18 14

다음으로, a [1] = 2 <13

스왑, 스왑 없음

2 5 13 18 14

3^rd iteration:

키 = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

스왑, 스왑 없음

2 5 13 18 14

4^th iteration:

키 = a [5] = 14

a [4] = 18> 14

18 및 14 스왑

2 5 13 14 18

다음으로, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

그래서 스왑 없음

2 5 13 14 18

드디어,

the sorted list is

2 5 13 14 18