삽입 정렬(Insertion Sort)

• 삽입 정렬(오름차순 기준)

-어느정도 정렬 되어 있는 상태에서 좋은 효율을 보여주는 정렬

-자신의 데이터와 앞자리 데이터를 비교해, 자신이 더 작으면 자리변경(앞자리 > 자신)

-자기보다 작은 데이터가 나오면 반복 종료

-다음 사이클로 넘어갈때, 한칸씩 뒤에 있는 데이터 부터 시작

이런 방식으로 마지막 자리 까지, 계속 반복

//삽입 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수))

void Sort::InsertSort(int *Array, const int Length)

{

        int target, j;

 

        for (int i = 1; i < Length; i++)

        {

               //현재 데이터 저장

               target = Array[i];

 

               //(현재 데이터 < 앞자리 데이터)라면 자리 변경

               for (j = i; j > 0 && Array[j - 1] > target; j--)

               {

                       //데이터를 뒤로 한칸씩 밀어냄

                       Array[j] = Array[j - 1];

               }

 

               //자리 변경이 없었으면 패스

               if (i == j)

                       continue;

 

               Array[j] = target;

        }

}