(삽입그룹) 삽입 정렬 / 셀 정렬

삽입 정렬은 기존에 정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입하는 정렬방식이다.

데이터 그룹은 다음과 같다

80, 50, 70, 10, 60, 20, 40, 30의 8개의 정수로 구성되어있다.

삽입 정렬에 의해 오름차순으로 정렬이 된다면...

두번째 자료부터 전체 자료개수만큼 루프를 돌면서 삽입위치를 찾는데..먼저 첫번째 80의 위치에

두번째 자료인 50의 삽입할 위치를 찾는것....일단 80보다는 작으니까..80앞에 50이 위치하게 된다.

그러면 50, 80, 70, 10, 60, 20, 40, 30 이렇게 되고..

다름 70을 50, 80의 그룹에 삽입될 위치를 찾고..50, 70, 80이 된다..반복하게 되는것...

50, 70, 80, 10, 60, 20, 40, 30 상태에서...다음인 10을 50, 70, 80 그룹에 삽입될 위치를 찾고..

C#

        void InsertSort(int[] value, int iSize)

        {

            int i = 0;

            int j = 0;

            int temp = 0;

            

            for(i = 0; i < iSize; ++i)

            {

                temp = value[i];

                j = i;

                

                //첫번째 i = 0일때는 안들어간다.

                //내부루프는 제일 뒤 자료부터 앞자료로 이동한다.

                //뒷자료부터 검색하는데 뒷자료가 현재 검색자료보다 크다면

                //현재위치에 큰 뒷자료를 넣고 그 뒷자료의 인덱스를 하나 줄인다

                while((j > 0) && value[j - 1] > temp)

                {

                    value[j] = value[j - 1];

                    j = j - 1;

                }

                value[j] = temp;

            }

        }

삽입 정렬은 정렬 전 자료의 상태에 따라 효율성의 차이가 무척 큰 정렬 알고리즘이다. 기존에 이미 정렬되어있다면 

1번씩 비교만 필요하고, 이동연산이 필요없으므로 O(n)이다. 최악인 역순이면 n^2이다.

정렬전 상태에 따른 효율성에 차이가 있지만, 빠른 정렬알고리즘이 아니다. 안정성유지됨..

---

셀 정렬은 기존 자료를 일정한 간격(인터벌 혹은 갭)에 의해 여러개의 부분 집합으로 나눈 다음, 각 부분 집합에 대해 삽입 정렬을 수행하여 전체 자료를

정렬하는 방식이다. 

기존 삽입 정렬이 어느정도 정렬이 된 자료에 대해서는 상당히 빠른 정렬 알고리즘이라는 점에서 착안되었다.

기존 자료를 일정한 간격으로 여러개의 부분집합으로 나누고 이에 대해 삽입 정렬을 하는데.. 일반적으로 초기 간격은 전체 자료 개수의 1/2로 설정한다.

자료그룹이 80, 50, 70, 10, 60, 20, 40, 30 의 8개 정수라면.. 간격은 4가 된다. 간격 4에 네개의 부분 집합으로 나누게 된다면..

80, 60 | 50, 20 | 70, 40 | 10, 30 이렇게 4개 부분집합이 나오게 되고 각 부분 집합에 대해서 각각에 대해 삽입정렬을 실행하면

60, 80 | 20, 50 | 40, 70 | 10, 30  최종 결과가 이렇게 나오게 되며 

60, 20, 40, 10, 80, 50, 70, 30이 1차 부분집합이 된 결과이다.

셀정렬은 기존 자료를 일정한 간격으로 여러개의 부분 집합으로 나누고 이에 대해 삽입 정렬을 실시하게 되는데.. 앞서 첫 번째 정렬에서의 초기 간격은 전체 자료 개수 1/2인 4였다. 일반적으로 셀 정렬에서 단계 별로 기존 간격의 1/2을 사용하기 때문에 두번째 정렬에서는 4의 1/2이니까 2가 된다.

즉 부분집합을 만들면

뭐...어쨌든 이런식인데..이게 삽입 정렬의 단점을 보완해서 나온 방식인데..

삽입 정렬의 단점은 만일 가장 멀리 떨어진 곳에서 비교가 이루어진다면 이동 시 많은 오버헤드가 발생될 수도...

C#

       void ShellSort(int[] value, int count)

        {

            int i = 0;

            int iInterval = 0;

            iInterval = count / 2;

            //인터벌이 1까지 되어야지 모든 항목에 대해서 삽입정렬이 된다.

            while(iInterval >= 1)

            {

                for(i = 0; i < iInterval; ++i)

                {

                    ShellInsertSort(value, i, count - 1, iInterval);

                }

                iInterval /= 2;

            }

        }

        void ShellInsertSort(int[] value, int start, int end, int interval)

        {

            int i = 0;

            int item = 0;

            int index = 0;

            //정렬의 범위가 start + interval부터 end까지이다. 

            //간격을 이용해서 정렬 대상을 선정하다.

            for(i = start + interval; i <= end; i += interval)

            {

                item = value[i];

                index = i - interval;   //간격을 이용해서 정렬 대상을 선정한다.

                

                while((index >= start) && item < value[index])

                {

                    //삽입 정렬하고 똑같은 알고리즘..

                    value[index + interval] = value[index];

                    index = index - interval;

                }

                value[index + interval] = item;

            }

        }

//코드 분석관련 추가 주석..

14) 이건 간격을 4로 나눌경우에 윗 글처럼 4개의 부분 집합이 생기니까 그거에 대한 for문이다

30) 이건 인터벌 간격만큼 총 갯수에서 얼마나 for이 돌아가야하는지를 나타낸것..그래서 초기값이 start에 인터벌이고

비교식이 총 갯수이고, 더하는값이 인터벌인 이유이다..start는 최초 시작위치를 표현함..짝을 이루기 위한 최초 시작위치라고해야하나.. 

31) 현재 삽입 정렬이 되어야하는 값을 임시저장해둔다.

32) 삽입 정렬이 되어야 하는 값의 인덱스에서 인터벌만큼 빼면 삽입 정렬과 비교를 해야할 처음값이 나오게 된다(이 인덱스를 통해서 아래

while문을 돌면서 index 위치를 수정하고 비교를하게 된다)

item이 삽입 정렬의 키 값이고...

index가 위치를 담당한다고 해야하나...

33, 34, 35) 최초 시작위치보다 항상 index는 같거나 커야한다( 그 이유는 기존 부분 집합의 제일 뒷자료에서 앞자료 순으로 이동해서 비교하니까..)

...그리고 삽입 정렬의 키가(item)이 위치를 담당하는 value[index]의 값보다 작으면

삽입 정렬의 키가 index에 들어와야한다. 왜냐면 오름차순에 의해서..

그래서..value[index + interval] = value[index]의 내용은...해당 위치 index에 있는 값이 더 크니까...

index + interval위치로 보내겠다는 것....그리고 index = index - interval을 함으로서 인덱스는 다시 인터벌 만큼 내린다..

오른쪽으로 간격만큼 이동하고..인덱스 값을 간격만큼 감소한다 

37) 여기까지 오게되면..위의 조건문 즉..item이 정확한 삽입정렬의 위치를 찾은(오름차순기준이다)것이므로..index + interval = item을 한다

그 이유는..내부에서 index = index - interval을 해주기 때문에..?