Member Avatar for Griff0527

I am trying to create a code that receives up to 50 integers from the keyboard, sorts the array from largest to smallest, then counts the instances of each number and displays the number inputted and the count of the number of instances. For example, if the number 11 was put in twice, the output would be:

N Count
11 2

If 11 were input 3 times and 55 twice, 1 once, then the output would be:

N Count
55 2
11 3
1 1

I believe that using a new two-dimensional array is the way to go, but can't sort out how to use a one-dimensional array to create a two dimensional array based on calculations. I have written the code to accept the input, fill the array, sort the input by swapping values, and a test output to show that that everything is functioning, but cannot determine how to create the output I desire. I believe the pseudo-code should be something like this:
function name: countArray

a[i] = b[i], c [j]  where i is the index, and j is a counter both initialized to zero
for (i = 0, i <= numberUsed, i++)
{
 if a[i+1] == a[i]
     c[j]++;
 else a[i+1] = b[i+1]
}

I have tried many variations of code to make this work and gotten so frustrated that I deleted each of my attempts. I am now posting "clean" code and on line 38 I have the comment "// SECOND ARRAY FILL GOES HERE"

can someone give me some idea of how the function definition, function call, and the guts of the function should look? I'd appreciate any insight.

#include <iostream>
#include <iomanip>
using namespace std;
const int MAX_ENTRIES = 50;

void fillArray(int a[], int size, int& numberUsed);
//Precondition: size is the declared size of the array a.
//Postcondition: numberUsed is the number of values  stored in a.
//a[0] through apnumberused-1] have been filled with
//nonnegative integers read from the keyboard.

void sortArray(int a[], int numberUsed);
//Precondition; numberUsed <= declared size of the array a.
//The array elementsa[p0] through a[numberUsed -1] have values.
//Postcondition: The values of a[0] through a[numberUsed -1] have
//been rearranged so that a[0] <= a[1].......<= a [numberUsed -1].

void swapValues(int& v1, int& v2);
//Interchanges the values of v1 and v2.

int indexOfLargest(const int a[], int startIndex, int numberUsed);
//Precondition: 0 <= startIndex < numberUsed.  Reference array elements
//have values.  Returns the index i such that a[i] is the largest of the 
//values a[startIndex], a[startIndex + 1], ..., a[numberUsed -1].

int main()
{
	int entry[MAX_ENTRIES], numberUsed; // variables used

	cout << "This program reads entries from the keyboard,\n"
		 << "fills an array, sorts the entered array, and\n"
		 << "outputs a two column list showing the number\n"
		 << "of times each value appears in the array.\n";

    fillArray(entry, MAX_ENTRIES, numberUsed); // fill array with input from user
	sortArray(entry, numberUsed); // sort array

	// SECOND ARRAY FILL GOES HERE


	//test output for sorted array
	for (int i = 0; i < numberUsed; i++)
	{
		cout << setw(12) << entry[i];
		cout << endl;
	}//end of test output for sorted array

	return 0;
}

void fillArray(int a[], int size, int &numberUsed)  // recieves data from the keyboard and stores it in the array
{
	cout << "Enter up to " << size << "numbers. When finished\n"
		 << "input 0 'zero' to mark your entries complete.\n";

    int next, index = 0;
	cin >> next;
	while ((next != 0) && (index < size)) // if input is '0', exits the input and returns to main
	{
		a[index] = next;
		index++;
		cin >> next;
	}

	numberUsed = index;
}

void sortArray(int a[], int numberUsed)  // sorts the array so values are arranged from largeest to largest
{
	int indexOfNextLargest;
	for (int index = 0; index < numberUsed -1; index++)
	{
		indexOfNextLargest = indexOfLargest(a, index, numberUsed); // calls function indexOfLargest to find the next largeest number
		swapValues(a[index], a[indexOfNextLargest]); // swaps the next largest value found by indexOfLargest, with the current value
	}
}

void swapValues(int&v1, int &v2) // simple swaping function to switch 2 values
{
	int temp;
	temp = v1;
	v1 = v2;
	v2 = temp;
}

int indexOfLargest(const int a[], int startIndex, int numberUsed) // searches the array to find the next largest value and returns the 
                                                                   // index of the value found to the sortArray function
{
	int min = a[startIndex], indexOfMin = startIndex;
	for (int index = startIndex +1; index < numberUsed; index++)
		if (a[index] > min)
		{
			min = a[index];
			indexOfMin = index;
		}

	return indexOfMin;
}

If the array is sorted, you can pretty much use the 2-D array technique efficiently. If not, it's as good as scanning the array for every index & counting it.

//This is when array is unsorted. 
int countArray(int *arr, int size)
{
  int count
  for(int i=0; i<size;i++)
  {
    count=0;
    int val=arr[i];
    for(int j=0; j<size;j--)
    {
      int match_val=arr[j];
      if(val==match_val)  //If array is sorted use "j=i+1" & "else break;" for optimization
        count++;
    }
    count--;  //As the same value will get counted too.
    cout<<val<<":"<<count;
  }
  return 1;  
}

If array is sorted & you want to store the count of it you can use a function that will store the count in their respective Index as the value & return that array. Example:

int *getArrayCounter(int *arr,int size)
{
  int *countStore = new int[size];  
  /*Same code with optimizations
   *Instead of cout use:
   *countStore[i]=count;
  */
return countStore;
}
Member Avatar for Griff0527

My initial array is sorting out properly as the test output on lines 41 through 46 display. I am really trying to figure out how to create the 2D array inside of a function based off the values and indexes of the initial 1D array. I'll study the code you posted and see if I can figure out how to make it work, but on the initial testing of it, it does not generate any output. I'm not understanding why you have count ++ followed by count--.

You should use the count() function from STL algorithm

#include <algorithm>

start = Vect.begin() ; 

end = Vect.end() ;
result = count(start, end, value) ;

(There is also a sort() function, but you shouldn't need it here)

If you wanted to do it more manually you should use an std::map.

Be sure to vote for cataloging answers like this, I've definitely answered this one before :) http://daniweb.uservoice.com/forums/62155-general/suggestions/830529-create-a-wiki-to-catalog-answers-and-examples-?ref=title

Dave

I'm not understanding why you have count ++ followed by count--.

This is to correct the value counting "itself".
EDIT: I changed code a bit, the position of count-- should be after the inside loop & reinitialize count.

>>I believe that using a new two-dimensional array is the way to go,
Why do you think so?

Member Avatar for Griff0527

I would think that a two dimensional array would be the way to go as well firstPerson. My reasoning (keep in mind that I'm still new to learning C++), is that Since I am wanting to format my output in two columns, it would make sense to create a 2D array with one column being equal to the values input (minus any duplicates) and the other column being the count of the number of times each value appears in the original array. At least, this was my intention and the reason I asked for assistance was to figure out how to create the 2D array.

That is exactly what a map does, except it doesn't waste space with numbers that have count = 0.

Member Avatar for Griff0527

Thank you David. I have never seen/used std::map so I am researching it now.

They are really, really useful! Try not to get caught up in the template/iterator terminology. The main idea is the key->value associations. In this case, the key is the number you want to know how many times has occurred, and the value is the number of times it has occurred. When you insert something into a map, if it is already in the map, nothing will happen. If you want to be able to map a key to multiple values, there is a std::multimap.

Let us know if you have any questions -

Good luck!

Dave

Member Avatar for Griff0527

Can you provide me a link to something that shows a similar task? Every example and literature I find on <map> is using it for a string and showing how to manually check for each string as opposed to integers and printing out the entire map.

Here is how to iterate through the whole map:

void IterateOverWholeMap()
{
  std::map <std::string, int> myMap;
  myMap["testone"] = 111;
  myMap["testtwo"] = 222;
  
  std::map<std::string,int>::iterator iter = myMap.begin();
    
  for(; iter != myMap.end(); ++iter) 
  {
   std::cout << iter->first << " " << iter->second << std::endl;
  } 
}

Here are some more notes I have:

void SetValue()
{
	//create a map
	std::map <std::string, int> MyMap;
	
	//create a mapping from "test" to 111
	MyMap["test"] = 111;
}

void SetAndGetValue()
{
	//create a map
	std::map <std::string, int> MyMap;
	
	//create a mapping from "testone" to 111
	MyMap["testone"] = 111;
	
	//create an iterator
	std::map<std::string,int>::iterator iter;

	//try to find "testone"
	iter = MyMap.find("testone");
	
	//we assume "testone" was found, so output the value that "testone" maps to
	std::cout << iter->second << std::endl;
}

void ResetValue()
{
	std::string Name = "testone";
	std::map <std::string, int> MyMap;
	MyMap[Name] = 111;
	
	std::map<std::string,int>::iterator iter;

	iter = MyMap.find(Name);
	
	double FirstValue = iter->second;
	std::cout << FirstValue << std::endl;
	
	MyMap[Name] = FirstValue + 1;
	
	double SecondValue = iter->second;
	std::cout << SecondValue << std::endl;
	
}

void NonExistentValue()
{
	std::map <std::string, int> MyMap;
	MyMap["testone"] = 111;
	
	std::map<std::string,int>::iterator iter;

	iter = MyMap.find("testone");
	
	if(iter == MyMap.end())
	{
		std::cout << "Element not found!" << std::endl;
	}
	else
	{
		std::cout << "Element found!" << std::endl;
		std::cout << iter->second << std::endl;
	}
}

Be sure to vote here: http://daniweb.uservoice.com/forums/62155-general/suggestions/830529-create-a-wiki-to-catalog-answers-and-examples-?ref=title so we can catalog examples like this!

Dave

Member Avatar for Griff0527

Thanks David, I looked this over, but this uses text as well. I'm trying to do this with two sets of integers. I think I'm about to go back to looking at the 2D option I started with. I am not sure if I should try to learn <map> and arrays at the same time. It seems to confuse me more to try to learn both at the same time. I will have to come back to <map> and figure it out though. I can see how it could be extremely useful.

Member Avatar for Griff0527

I hate to beat a dead horse, but can someone assist me in figuring out how to write a function that will accept the 1D array that is created by the users input and then generate a 2D array without using <map>? I have been working on this for about 3 days and cannot figure it out. I have deleted my attempts multiple times as I can't sort out the actual function call and the errors I receive. I am going to attempt it again. In my original post I stated all of the code I have written as well as a pseudo-code for how I believe my last function call needs to be programmed, but I am having an issue converting the pseudo-code to C++.

You really shouldn't be scared of STL containers. They will save you tremendous amounts of time (in exactly cases like this!) Rather than thinking of it as "learning maps and arrays at the same time" you should see this as an opportunity not to get stuck in the array way of thinking of things (as I had done for years before I was introduced to STL containers!) and consider it a good time to learn about containers/data structures. There is not really a hierarchy (array before set, before map, etc) - they are all on equal ground, just have different uses.

If I couldn't use a map, my second option would be this:

1) Store the input array in an std::vector.
2) Copy the input vector into a std::set. This removes all duplicate elements
3) Create a vector the same size as the set. This is where you will store the count of each unique element
4) Iterate over the set and use std::count (from STL <algorithm>) on the original vector, searching for the current element in the set
5) Store the result in the ith position of the vector you created in step 3.

This is exactly what a map would be doing :)! The algorithm would be much more involved if you only wanted to use arrays (vectors), as you'd have to do the uniqueness checking and counting manually.

Good luck,

Dave

Making a 2d array for this is pretty strait forward. Because you don't know how many duplicates are in the array you would need to have an array like

int ** twoDarray = new int*[size];
for (i = 0; i < size; i++)
    towDarray[i] = new int[1];

Now all you have to do is loop through the array with a for loop that has two separate counter. One will be for the one D array and the other will be for the 2d array. Something like this

int counter = 0;
for (int i = 0, j = 0; i < size; i++)
{
    //...
}

As you are going through the loop test to see if the element at oneD is the same as the previous element and if it is increment counter. If it is not than then store the counter into twoDarray[j][0], then reset counter to 0 and then increment j. This isn't very elegant but it should get the job done.

Member Avatar for Griff0527

David,
I understand what you are saying and I agree. However, this program is an assignment for an online college and I am trying to not use things that are too far ahead in the book. <map> is covered about 620 pages in the future of the book from where I am. That being said, I wrote a function that "should" do what I am wanting but I am getting partial gibberish for my output. The first number feeds into the sorted arrays properly, but the rest of the output is random information stored in the memory allocation, so I know my logic between lines 118 and 126 is flawed in some way. Will you (or anyone else reading this post) please assist me in finding my logical error? The code compiles and runs just fine except for my output.

#include <iostream>
#include <iomanip>
using namespace std;
const int MAX_ENTRIES = 50;

void fillArray(int a[], int size, int& numberUsed);
//Precondition: size is the declared size of the array a.
//Postcondition: numberUsed is the number of values  stored in a.
//a[0] through apnumberused-1] have been filled with
//nonnegative integers read from the keyboard.

void sortArray(int a[], int numberUsed);
//Precondition; numberUsed <= declared size of the array a.
//The array elementsa[p0] through a[numberUsed -1] have values.
//Postcondition: The values of a[0] through a[numberUsed -1] have
//been rearranged so that a[0] <= a[1].......<= a [numberUsed -1].

void swapValues(int& v1, int& v2);
//Interchanges the values of v1 and v2.

int indexOfLargest(const int a[], int startIndex, int numberUsed);
//Precondition: 0 <= startIndex < numberUsed.  Reference array elements
//have values.  Returns the index i such that a[i] is the largest of the 
//values a[startIndex], a[startIndex + 1], ..., a[numberUsed -1].
void displayArray(int entry[], int numberUsed, int store[], int count[]);
//Sort and output the count of each instance


int main()
{
	int entry[MAX_ENTRIES], numberUsed; // variables used
	int store[MAX_ENTRIES], count[MAX_ENTRIES];
	
	cout << "This program reads entries from the keyboard,\n"
		 << "fills an array, sorts the entered array, and\n"
		 << "outputs a two column list showing the number\n"
		 << "of times each value appears in the array.\n";

    fillArray(entry, MAX_ENTRIES, numberUsed); // fill array with input from user
	sortArray(entry, numberUsed); // sort array



	displayArray(entry, numberUsed, store, count);

/*	for (i = 0; i <= numberUsed; i++)
	{
		b[i] = a[i];
		j = 1;
		if (a[i] == a[i+1])
		{
			c[i] = j+1
		}
	}
*/
	return 0;
}

void fillArray(int a[], int size, int &numberUsed)  // recieves data from the keyboard and stores it in the array
{
	cout << "Enter up to " << size << "numbers. When finished\n"
		 << "input 0 'zero' to mark your entries complete.\n";

    int next, index = 0;
	cin >> next;
	while ((next != 0) && (index < size)) // if input is '0', exits the input and returns to main
	{
		a[index] = next;
		index++;
		cin >> next;
	}

	numberUsed = index;
}

void sortArray(int a[], int numberUsed)  // sorts the array so values are arranged from largeest to largest
{
	int indexOfNextLargest;
	for (int index = 0; index < numberUsed -1; index++)
	{
		indexOfNextLargest = indexOfLargest(a, index, numberUsed); // calls function indexOfLargest to find the next largeest number
		swapValues(a[index], a[indexOfNextLargest]); // swaps the next largest value found by indexOfLargest, with the current value
	}
}

void swapValues(int&v1, int &v2) // simple swaping function to switch 2 values
{
	int temp;
	temp = v1;
	v1 = v2;
	v2 = temp;
}

int indexOfLargest(const int a[], int startIndex, int numberUsed) // searches the array to find the next largest value and returns the 
                                                                   // index of the value found to the sortArray function
{
	int min = a[startIndex], indexOfMin = startIndex;
	for (int index = startIndex +1; index < numberUsed; index++)
		if (a[index] > min)
		{
			min = a[index];
			indexOfMin = index;
		}

	return indexOfMin;
}

void displayArray(int entry[], int numberUsed, int store[], int count[])
{
		//test output for sorted array
	for (int i = 0; i < numberUsed; i++)
	{
		cout << setw(10) << entry[i];
		cout << endl;
	}
	cout << endl << endl;//end of test output for sorted array
	
	int j = 0;
	store[j] = entry[j];
	for (int j = 0; j <= numberUsed; j++)
	{
		if (entry[j] = entry[j]++)
			count[j+1];
		else
			entry[j]++;
	}
	cout << setw(10) << "Number"
		 << setw(10) << "Count\n";
	
	for (j = 0; j <= numberUsed; j++)
	{
		cout << setw(10) << store[j] << setw(10) << count[j] << endl;
	}

}

instead of what you have on lines 118 through 126 try doing this

int counter = 1;
for (int i = 1, j = 0; i < numberUsed; i++)
{
    if (entry[i] == entry[i - 1])
        counter++;
    else
    {
        store[j] = entry[i - 1];
        count[j] = counter;
        counter = 1;
        j++;
    }
}
commented: Provided an excellent example that still required me to correct my own errors +1
Member Avatar for Griff0527

Brilliant! That's exactly what I was trying to do. I see my mistakes in my line 118-126 now as well. I used your suggestion, tested it, and had to make a few tweaks to it in order to get the correct output. Thank you for putting me on the right track Nathan. The final working section (118-132 after edits) looks like

int counter = 1;
	int line = 0;
    for (int i = 0, j = 0; i < numberUsed; i++)
    {
		if (entry[i] == entry[i + 1])
			counter++;
		else
		{
			store[j] = entry[i];
			count[j] = counter;
			counter = 1;
			j++;
			line++;
		}
      }

As you can see, I ended up setting i =0 for the first portion, adding an int called "line" to keep count for my output, and changing the comparison in the first if statement (due to changing the variable i to 0 during my debugging efforts). I appreciate you clarifying my logic error on this issue.

No problem glad to help.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.