삽입정렬

쉘 정렬 보다가 삽입정렬 기반인거 보고 겸사겸사 정리

 

이런식으로 차례대로 우겨넣는 정렬법

자기차례가 되면 넣어져있는 값들과 비교해나가면서 자신이 갈 수 있는 최대한 앞으로 자리를 잡아서 들어간다

 

1번째 인덱스부터 자기 앞에있는 숫자보다 더 작으면 계속 앞으로 배치한다

갈 수 있는 최대한 앞으로 갔으면 그 다음 인덱스로 넘어가고, 이걸 마지막 인덱스까지 반복 

class InsertSorter
    {
        public static int[] SortData(int[] data)
        {
            int[] sort = data;

            //들어있는 숫자 전부 순환하는 반복(0번째 인덱스는 어차피 더 앞으로 갈수가 없으니까 1번째부터 시작하는게 나음)
            for (int i = 1; i < data.Length; i++)
            {
                //기준 숫자 앞에있는 숫자들과 하나씩 비교하는 반복
                for (int j = i; j > 0; j--)
                {
                    //자리를 교환하는게 아니라, 비집고 들어가는 거라 순차적으로 한칸씩 계속 교환을 하면서 앞으로 가야함
                    if (sort[j] < sort[j - 1])
                    {
                        int temp = sort[j - 1];
                        sort[j - 1] = sort[j];
                        sort[j] = temp;
                    }
                    //갈 수 있는 최대치에 도달하면 반복 중단
                    else break;
                }

                foreach (int num in sort)
                    Console.Write(num.ToString() + " ");
                Console.WriteLine();
            }

            return sort;
        }
    }

 

실행 결과 예시

구현이 간편하고 최적의 경우 O(n-1)의 속도를 자랑하지만 이건 어디까지나 "최적" 이다

지금 실행한 예시는 정렬할 데이터 수가 적어서 상관없지만...

데이터가 만개가 되면 이렇게되고,

3만개가 되면 이렇게 된다

 

이런 속도문제를 해결한게 쉘 정렬이라고 보면 될 듯 하다

거의 100배 이상 빨라진 걸 볼 수 있다

물론 이 차이는 데이터가 많으면 많을수록 더 크게 벌어진다

다음글에선 이 쉘 정렬을 간단하게 정리하는걸로