알고리즘 스터디 - 3

박준영·2020년 3월 8일
0

알고리즘스터디

목록 보기
3/4

정렬 알고리즘 (Sort)

  • 삽입정렬 알고리즘 (Insertion Sort)

삽입정렬 알고리즘 (Insertion Sort)

각 숫자를 적절한 위치에 삽입하자.

#include <stdio.h>

int main(void)
{
    int i, j, temp;
    int array[10] = {1, 10, 4, 6, 5, 2, 3, 9, 8, 7};

    for (i = 0; i < 9; i++)
    {
        j = i;
        while (array[j] > array[j + 1])
        {
            temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
            j--;
        }
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d", array[i]);
    }

    return 0;
}

✍ Insertion Sort의 효율성 ✍

  • 삽입정렬은 기본적으로 이미 정렬되어 있다는 가정하에 이루어 지는 정렬방법이다.

속도면에서는 지금까지 공부한 선택정렬과 버블정렬에 비해선 빠른편이다. 이미 정렬이 되어있다는 가정 덕분에 필요할때만 위치를 바꿔주게된다. 따라서 이미 어느정도 정렬이 되어있는 데이터라면 삽입정렬을 이용할 시 상당히 빠른 속도로 정렬시킬수있다.

0개의 댓글