끄적끄적

배열은 O(N)이다.

배열은 삽입, 삭제, 검색을 할 때 O(N) 즉 loop를 한번 돈다. 아주 기본 중 기본..

C언어로 삽입, 삭제의 알고리즘 코드를 작성해보자.

배열의 삽입(우로밀착)

int nums[8];
size_t max_count = 0;

void insert_at(size_t index, int number)
{
	size_t i;

	// 우로밀착 코드
	for(i = max_count; i > index; i--)
	{
		nums[i] = nums[i-1];
	}

	nums[index] = number;
	++max_count;
}

void main()
{
	insert_at(0, 1);
	insert_at(0, 2);
	insert_at(0, 3);
	insert_at(0, 4);

	delete_at(0);
	size_t i;
	for (i = 0; i < MAX_NUMS; i++)
	{
		printf("%d\n", nums[i]);
	}
}

배열의 삽입이 0번째 인덱스 즉 가장 첫번째 자리에서 이뤄진다면 0번째 인덱스를 기준(현재 인덱스 포함)으로 오른쪽에 있는 모든 요소들은 우로밀착! 오른쪽으로 한 칸 이동 해야한다. 그래서 for loop가 필요하다.O(N)

배열의 삭제(좌로밀착)

void delete_at(size_t index)
{
	size_t i;
	for (i = index; i < max_count; i++)
	{
		nums[i] = nums[i + 1];
	}
	--max_count;
}

배열의 삭제가 0번째 인덱스에서 이뤄진다면 0번째 인덱스를 기준으로 좌로 한칸씩 밀착해야 한다.