알고리즘 가이드 학습 1 - 삽입 정렬 (insertion sort)

문서 목록

설명

비내림차순 정렬 1

비내림차순 정렬 2

오름차순 정렬 없음 1

오름차순 정렬 없음 2

이분법 추가

요약

설명
다음은 을 공부하는 과정에서 필기하고 정리한 것이다. 채소 새급은 정신을 가다듬지 마라.
내림차순이 아닌 정렬 1
다음 코드는 책의 위조 코드에 따라 편집된 원본으로 이 방식은 비강하 순서로 정렬된다.

void insertionSort_1(int *a, int length)
{
    for(int j=1; j=0 && a[i] > key)
        {
            a[i+1] = a[i];
            i--;
        }

        a[i+1] = key;
    }
}

내림차순이 아닌 정렬 2
다음 코드는 배열 끝에서 순서를 재정의하는 비내림차순 정렬입니다.

void inserttionSort_2(int *a, int length)
{
	for(int j=length-2; j>=0; j--)
	{
		int key = a[j];
		int i = j + 1;
		while(i<=length-1 && a[i] < key)
		{
			a[i-1] = a[i];
			i++;
		}
		a[i-1] = key;
	}
}

오름차순 정렬 없음 1
다음 코드가 고쳐진 비승차순 정렬입니다.

void insertionSort_3(int *a, int length)
{
    for(int j=1; j<length; j++)
    {
        int key = a[j];
        int i = j - 1;

        while(i>=0 && a[i] < key)
        {
            a[i+1] = a[i];
            i--;
        }

        a[i+1] = key;
    }
}

오름차순 정렬 없음 2
다음 코드는 수조의 끝에서부터 고쳐진 비승차순 정렬입니다.

void insertionSort_4(int *a, int length)
{
    for(int j=length-2; j>=0; j--)
    {
        int key = a[j];
        int i = j + 1;

        while(i<= length-1 && a[i] > key)
        {
            a[i -1] = a[i];
            i++;
        }

        a[i-1] = key;
    }
}

이분법 추가

void insertionSort_5(int *a, int length)
{
    for(int j=1; j<=length-1; j++)
    {
        int key = a[j];
        int m = (j-1)/2;

        if(a[m] > key)
        {
            for(int t=j-1; t>=m; t--)
            {
                a[t+1] = a[t];
            }
            int i = m -1;
            while( i>=0 && a[i] > key)
            {
                a[i+1] = a[i];
                i--;
            }

            a[i+1] = key;
        }
        else
        {
            int i = j - 1;
            while(i>m && a[i] > key)
            {
                a[i+1] = a[i];
                i--;
            }
            a[i+1] = key;
        }
    }
}

총결산
첫 번째는 책에서 위조 코드를 번역한 원본 코드이고, 다른 세 가지는 이를 바탕으로 개작한 코드이다.같은 것은 사상이다. 다른 것은 조작의 시작점과 순서의 규칙이 다르다는 것이다.이 몇 가지는 형식적으로 for순환은 수조에서 원소를 옮겨다니는 작업을 완성하고while순환은 판정된 원소의 삽입 위치를 찾아 원소를 이동하는 두 가지 작업을 완성한다.그룹 헤더에서 시작하는 방법은 for 순환에서 j의 계수가 작은 것에서 큰 것으로 대응하는 것이다.그룹 끝에서 시작하는 방법, for 순환에서 j의 계수는 크고 작습니다.그 중에서 a[j]는 삽입된 원소를 추출하고 i의 시작값은 j에 의존하며 수조에서 j와 인접한 정렬된 방향에 있는 원소의 하표이다.while 순환 중 요소와 키를 비교한 후 이동 방향도 시작단에서 멀리 떨어진 방향입니다.