[#9] Insert Sort : 삽입 정렬

삽입 정렬

https://wonjayk.tistory.com/218

비교 대상이 될 데이터를 선택한 후 해당 데이터를 특정한 기준에 맞춰 적당한 곳에 삽입하고 다시 정렬하는 것을 삽입 정렬이라 한다.

 

일반적으로 버블 정렬과 시간복잡도는 비슷하지만 이미 정렬되어 있을 경우 반복문을 생략할 수 있으므로 버블 정렬보다 더 효율적이다. 아래 코드는 오름 차순을 구현한 코드이다. 

 

 

---

 

전체 코드

#include <iostream>
#include <cstring>

void InsertionSort(int DataSet[], int Length)
{
	int value = 0;

	for (int i = 1; i < Length; i++)
	{
		if (DataSet[i - 1] <= DataSet[i])
		{
			for (int i = 0; i < Length; i++)
				std::cout << DataSet[i] << ' ';
			std::cout << std::endl;
			continue;
		}
		value = DataSet[i];

		for (int j = 0; j < i; j++)
		{
			if (DataSet[j] > value)
			{
				// memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));
				for (int k = i; k > j; k--)
					DataSet[k] = DataSet[k - 1];
				DataSet[j] = value;
				break;
			}
		}
	}
}

int main(void)
{
	int DataSet[] = { 6, 4, 2, 3, 1, 5 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	
	InsertionSort(DataSet, Length);

	for (int i = 0; i < Length; i++)
		std::cout << DataSet[i] << ' ';
	std::cout << std::endl;

	return 0;
}

 

memmove 함수

순환문은 j인덱스부터  value의 값보다 작은 값들을 한칸 씩 밀기 위해 동작하고 있는데 이 과정을 memmove함수로 간단히 할 수 있다. memmove 함수의 원형 첫번째 매개변수는 데이터가 이동될 메모리 위치이고 두번째 매개변수는 데이터를 이동시킬 메모리의 위치이다. 세번째 매개변수는 해당 데이터의 크기이며 위에 알고리즘은 i - j만큼의 크기, i보다 작고 자신보다 큰 인덱스들을 모두 이동시킨다는 의미이다.

https://blockdmask.tistory.com/444 

 

---