[알고리즘]삽입정렬(InsertionSort)

삽입정렬(Insertion Sort)

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

배열의 모든 데이터들을 앞에서부터 차례대로 정렬시키면서 나아가는 방식입니다.

즉, 앞에서부터 차례대로 정렬해 나간다고 보면 되겠습니다.

위키 참고하면 많은 도움이 되실꺼에요. <- 클릭하면 이동합니다.

위키를 보시면 memcpy()를 사용했을 때 25~30% 빠르게 처리된다고 합니다.

삽입정렬 알고리즘의 작동 과정은 다음과 같습니다. (Swap을 하여 처리하는 경우입니다)

< [ 4, -8, 3, 1 ] 정렬 >

위 그림을 보시면 앞에서부터 정렬이 되어 갑니다.

이렇게 순차적으로 정렬을 해 나가면서, 

자신과 비교후 조건이 충족되면 자기 자신을 앞에다 삽입을 합니다.

위를 코드로 보시면 다음과 같습니다.

< C++ 코드 >

#include 
using namespace std;

void insertionSort(int arr[], int length)
{
	int i, j, tmp;
	for(i = 1; i < length; i++)
	{
		j = i;
		while(j > 0 && arr[j - 1] > arr[j])
		{
			tmp = arr[j];
			arr[j] = arr[j - 1];
			arr[j -1] = tmp;
			j--;
		}
	}
}

int main()
{
	int values[] = {4, -8, 3, 1};

	cout << "Before sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}

	// sort
	insertionSort(values, 4);
	cout << "After sorting" << endl;
	for(int i = 0; i < 4; i++)
	{
		cout << values[i];
		if(i < 3)
			cout << ", ";
		else 
			cout << endl;
	}
}

< 결과 >

잘못된 부분이 있으면 언제든 리플해주시기 바랍니다.

참고 : http://www.algolist.net/Algorithms/Sorting/Insertion_sort