C++ Implementation using an Array

This is the fourth blog entry in the sequence that deals with a conversation with a couple colleagues.

This blog entry shows the implementation using the C++ programming language for the problem described in the first blog entry using an array. As in the previous blog entry, let’s first look at the code used to implement the main() function.

int main ()
{

	int		myArray[N]	= {},
			element		= 0,
			pos		= 0;

	// **** initialization ****

	for (int i = 0; i < N; i++)
	{
		myArray[i] = 0;
	}

	// **** ****

	cout << "<<< inserting ..." << endl;

	// **** start timing ****

	clock_t	begin = clock();

	// **** populate array with random values ****

	for (int i = 0; i < N; i++)
	{

		// **** generate random integer in specified range ****

		element = NextInt();

		// **** insert value into array (sorted ascending order) ****

		InsertElement(myArray, element);

		// **** display array ****

		DumpArray(myArray);
	}

	// **** ****

	cout << "<<< removing ..." << endl;

	// **** loop removing elements from random positions ****

	for (int i = 0; i < N; i++)
	{

		// **** generate random position ****

		pos = RandomPosition(N - i);

		// **** remove element from array ****

		RemoveElement(myArray, pos);

		// **** display the array ****

		DumpArray(myArray);
	}

	// **** compute the elapsed time ****

	clock_t	end = clock();
	double	elapsedTime = double(end - begin) / CLOCKS_PER_SEC;

	// **** display we are done ****

	cout << "<<< array done N: " << N << " elapsedTime: " << elapsedTime << endl;

	// **** ****

	return 0;
}

The first loop is used to populate the array with N random numbers. The random numbers are in the range from 1 to 999. That may easily be changed by altering the value of a constant in the program. The first function in the loop generates a random integer and the second inserts the integer into the array at the proper position. The requirement calls for keeping the sequence of integers in the array in ascending order. For verification purpose, we invoke a third function to display the contents of the array after an element is inserted.  This is used to visually verify that the mechanism is working properly.

The second loop generates a random position in the array to be used to remove an element.  It is followed by a function that removes the element from the array at the specified position. The function used to display the array to verify the proper operation of the removal mechanism is then called.

Following is the code used by the InsertElement() function to insert the random generated integer element into the array at the proper location in order to keep its contents sorted in an ascending order.

void	InsertElement(int array[], int element)
{

	int	i	= 0;

	// **** check if the array is full ****

	if (array[N - 1] != 0)
	{
		cout << "<<< array is full :o(" << endl;
		return;
	}

	// **** search for position to insert ****

	for (i = 0; (array[i] != 0) && (i < N) && (array[i] < element); )
	{
		i++;
	}

	// **** move elements down ****

	memmove((void *)&array[i + 1], (void *)&array[i], ((N - 1) - i) * sizeof(int));

	// **** insert element ****

	array[i] = element;
}

First a check is made to determine if the array is full. There is no real reason to do so because of the way the program is designed.  If so, the function displays a message and returns.

If the array is not full, the loop is used to look for the proper location at which the new element should be inserted.  When the position in the array is found, the contents under the specified position are moved down. The element is then inserted at the proper position in the array.

The code for the function RemoveElement() used to remove an element from the vector at a random position follows.

void	RemoveElement(int array[], int pos)
{
	memmove(&array[pos], &array[pos + 1], ((N - 1) - pos) * sizeof(int));
	array[N - 1] = 0;
}

The elements at positions below the one specified are pushed up. In essence that removes the desired element from the array.

As in the other examples, the RandomPostion() function generates a random number in the range of elements in the specified array.

int	RandomPosition(int totalElements)
{
	return randGen() % totalElements;
}

NextInt() as the RandomPosition() are convenience functions. The NextInt() function generates a random value for an element to be inserted into the array.

int	NextInt()
{
	return minRand + (randGen() % maxRand) - minRand;
}

An array is probably not the first data structure that a developer would think of to address the requirements stated for the program. It was just added to this mix because of previous experience using an implementation of an ArrayList for a project that needed a fast mechanism to check for duplicates (for sanity reasons), insert, search and delete data structures holding network information (i.e., socket, TCP/IP, time stamp).

The fifth and last entry in this sequence of blogs contains some timing for the different implementations.

In the next blog, a similar implementation based on arrays is presented.

John Canessa