정렬알고리즘_삽입정렬

삽입정렬

 

많은 비교와 적은 교환으로 특징인 선택 정렬과 반대로 적은 비교와 많은 교환이 이루어지는게 특징이다.

 

삽입 정렬의 전략

이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다.

[루프안에 a[i]보다 t를 쓰는것이 더 빠르다(단순히 t의 값만 읽어 오기 때문)]

삽입정렬은 안정성이 있는데, 항상 그런것은 아니다. (>=t 경우)

 

이미 정렬된 배열일 경우 매우 빠른 속도를 가진다.

이미 정렬된 경우에는 삽입 정렬의 실행 시간은 N에 비례하는 선형적인 특성을 가진다.

 

둘째로 삽입 정렬은 역순의 경우 최악의 경우가 된다. 이동과 비교의 횟수는 N*(N-1)/2가 되어서 선택 정렬보다 속도가 떨어진다.

삽입 정렬의 최적화

a[0]값에 -1을 집어넣고 실제 값들은 이후의 저장하도록 하자

그러면 while문에 루프의 판단문에서 j>0과 같은 비교문을 하나 없앨 수 있다.

이런 방법을 사용하게 되면 정렬의 실행시간이 약간 단축되고 N이 클 경우 더 단축

(키값의 최소값을 정하지 못하는 경우가 있기 때문에 신중히 사용해야한다.)

 

간접정렬

교환이 많은 삽입정렬이기에 간접정렬이 고려된다.

레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스의 배열을 조작하는 방법

비교는 실제 배열a이 하지만 while루프 내의 교환 작업은 index배열을 사용한다.

a에는 아무 변화가 없지만 index배열에는 정렬된 순서가 저장되어 있다.

제일 첫 번째 레코드가 무엇인지 알려면 a[index[0]]와 같이 접근 하면 알 수 있다.

 

실제로 a 배열을 정렬 하려면 아래와 같은 함수가 필요할 것이다.

 

학습참고 : C로배우는 알고리즘