c프로그래밍 삽입정렬(Insertion Sort) c코드 설명

컴퓨터 알고리즘에서 정렬은 기본개념이면서 누구나 알아야되는 기본상식입니다.

이러한 정렬방법에도 시간복잡도가 차이가 나는데요.

버블정렬 삽입정렬 퀵정렬  병합정렬 힙정렬 등 다양한 정렬이 존재합니다.

그 중 삽입정렬에 대해 알아보겠습니다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1 10 5 8 7 6 4 3 2 9 라는 수들을 오름차순으로 정렬하시오

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

삽입정렬의 경우 위 문제에서 각 숫자를 적절한 위치에 삽입하는 방법으로

문제를 해결합니다. 여기서 애매한 표현은 '적절한 위치'인데요

 

for( int i=0; i<n; i++)

{

key = arr[i];

j = i-1;

 

while(j>=0 && arr[j] > key)

{

arr[j+1] = arr[j];

j--;

}

stt[j+1] = key;

}

삽입정렬(insertion sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식입니다.

삽입 정렬(insertion sort) 알고리즘 개념 요약
손안의 카드를 정렬하는 방법과 유사하다.
새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
삽입 정렬(insertion sort) 알고리즘의 구체적인 개념
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
처음 Key 값은 두 번째 자료부터 시작한다.

 

 

 

 

정리. 

1. 정렬된 partial 어레이를 유지하며 한칸씩 늘려가며 정렬

2. 한칸 늘릴 때 새로 삽입된 데이터를 정렬된 어레이에서 맞는자리로 위치시킨다.

3. 탐색 범위 outer : 1 ->n      inner : j >=0 && arr[j] >key