Arrays

[RaCheer]

I am writing a program that allows the user to insert numbers and then the program sorts them into ascending order. I have this accomplished, however, I also need an array to count the number of times each number the user inserts occurs. For ex: Say the user inserts 3 6 7 6 1. I need the array to keep count of the number of times these numbers occur. I also need to display the number/numbers that occur the most. I have struggled with these issues for the past few days and am not very good with arrays. I would really appreciate any help you could offer. Thank you!

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void sort(int a[], int number_used);
void swap_values(int& v1, int& v2);
int index_of_smallest(const int a[], int start_index, int number_used);
int count = 0;
int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 int sample_array[100], number_used;
 fill_array(sample_array, 100, number_used);
 sort(sample_array, number_used);
 cout << "\n";
 cout << "\n";
 cout << "Numbers\t";
 cout << "Times" << endl;
 for (int index = 0; index < number_used; index++)
  {
   cout << sample_array[index] << "\t";
   cout << "Count will go here." << endl;
  }
 cout << endl;
 cout << "\n";
 cout << "You entered " << count << " numbers." << endl;
 return 0;
}
int fill_array(int a[], int size, int& number_used)
{
 cout << "Enter up to " << size << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  int next, index = 0;
  cin >> next;
  while ((next >= 0) && (index < size))
  {
   a[index] = next;
   index++;
   cin >> next;
   count++;
  
  }
  number_used = index;
  return count;
}
void sort(int a[], int number_used)
{
 int index_of_next_smallest;
 for (int index = 0; index < number_used - 1; index++)
 {
  index_of_next_smallest = index_of_smallest(a, index, number_used);
  swap_values(a[index], a[index_of_next_smallest]);
 }
}
void swap_values(int& v1, int& v2)
{
 int temp;
 temp = v1;
 v1 = v2;
 v2 = temp;
}

int index_of_smallest(const int a[], int start_index, int number_used)
{
 int min = a[start_index], 
  index_of_min = start_index;
 for (int index = start_index + 1; index < number_used; index++)
  if (a[index] < min)
  {
   min = a[index];
   index_of_min = index;
  }
 return index_of_min;
}

[ft3ssgeek]

for the first problem, counting the number of times each number occurs in the array, you want to creat a second array that is the same size as the first one. Initialize all cells in this new array to 0. Pass both of those arrays to your counting function. You will have two loops, one inside the other. The first loop will loop through the second array, and the second loop will loop through the first array. By comparing the value of the cell in the first array that corresponds to the cell the second array is currently on, testing each value in the first array and incrementing the value in the second array by one each time you have a match, you will end up with the second array being populated with the number of times each number occured in the first array.

for(int i=0;i<asize;i++){
    for(int j=0;j<asize;j++){
        if(arr1[i]==arr1[j])
            arr2[i]++;
        }
    }
}

This oughta get you going again...hope it helps...

[RaCheer]

Ok...I have tried out your suggestion and so far I have it working without any compilation errors. However, I get some pretty crazy numbers in my counter column in the results. Here is my new code:

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void sort(int a[], int number_used);
void swap_values(int& v1, int& v2);
int index_of_smallest(const int a[], int start_index, int number_used);
int count_array(int sample_array[], int counter[], int number_used);
int count = 0;
int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 int sample_array[100], number_used;
 int counter[100];
 fill_array(sample_array, 100, number_used);
 count_array(sample_array, counter, number_used);
 sort(sample_array, number_used);
 cout << "\n";
 cout << "\n";
 cout << "Numbers\t";
 cout << "Times" << endl;
 for (int index = 0; index < number_used; index++)
  {
   cout << sample_array[index] << "\t";
   cout << counter[index] << endl;
  }
 cout << endl;
 cout << "\n";
 cout << "You entered " << count << " numbers." << endl;
 return 0;
}
int fill_array(int a[], int size, int& number_used)
{
 cout << "Enter up to " << size << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  int next, index = 0;
  cin >> next;
  while ((next >= 0) && (index < size))
  {
   a[index] = next;
   index++;
   cin >> next;
   count++;
  
  }
  number_used = index;
  return count;
}
void sort(int a[], int number_used)
{
 int index_of_next_smallest;
 for (int index = 0; index < number_used - 1; index++)
 {
  index_of_next_smallest = index_of_smallest(a, index, number_used);
  swap_values(a[index], a[index_of_next_smallest]);
 }
}
void swap_values(int& v1, int& v2)
{
 int temp;
 temp = v1;
 v1 = v2;
 v2 = temp;
}

int index_of_smallest(const int a[], int start_index, int number_used)
{
 int min = a[start_index], 
  index_of_min = start_index;
 for (int index = start_index + 1; index < number_used; index++)
  if (a[index] < min)
  {
   min = a[index];
   index_of_min = index;
  }
 return index_of_min;
}
int count_array(int sample_array[], int counter[], int number_used)
{
 for(int index=0; index<number_used; index++)
 {
  for(int index2=0; index2<number_used; index2++)
  {
   if (sample_array[index]==sample_array[index2])
    counter[index]++;
  }
  return counter[index];
 }
 
}

And this is the strange result I get:

Numbers Times

1 -858993548
3 -858993460
3 -858993460
5 -858993460
6 -858993460


Any help in cleaning up my mess would be appreciated! I am also still wondering how to display the number/numbers that occur the most. Thank you!

[John A]

You might want to initialize your counter array.

[ft3ssgeek]

exactly...what have you got so far on your code to display the number(s) that occur the most?

[RaCheer]

Ok...I initialized the array to zero like so:

int counter[100] = {0};

But now in the result it only tells how many times the first number was displayed. The other numbers display 0 times:

Numbers Times

1 1
2 0
3 0

Why is this?

Also, I do not have anything in my code yet to display the number(s) that occur the most. I was wondering how to go about that. I am learning more with your help! Thank you!

[John A]

>Why is this?
Because you misplaced your return statement.

int count_array(int sample_array[], int counter[], int number_used)
{
    for(int index=0; index<number_used; index++)
    {
        for(int index2=0; index2<number_used; index2++)
        {
            if (sample_array[index]==sample_array[index2])
                counter[index]++;
        }
        return counter[index]; // drop this down below the }
    }
}

Why are you even using a return statement at all? It's not like the last element in the array is going to be very useful without the other values...

And by the way you may want to consider using a debugger, they make errors like these really easy to spot.

[ft3ssgeek]

Ok...looking through your code I don't see anything wrong with the counter function...One thing to note though, is that you don't need a return value for that counter function...arrays automatically get passed by reference...you could have just as easiler used the following function header:

void count_array(int sample_array[], int counter[], int number_used)

and not returned a value...I just compiled a small test program on my computer and it ran the code just fine...you might try using void instead and recompiling and see how it goes...
As for the other problem (which number occurs the most...once you get your second array (the one with the count of numbers) you will have your number(s) that occur the most...You just need to figure out how to use it...

[ft3ssgeek]

ahh, ok, good catch joe...

[RaCheer]

Wonderful...it now works! I will continue to work on displaying the numbers that occur the most often.

I have another question though. I have used a selection sort to sort the numbers into ascending order. Out of curiosity, how could I change it to an insertion sort, so that a number is sorted into place as soon as the user enters it? It seems it would make more sense to di it this way. Thank you!

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void sort(int a[], int number_used);
void swap_values(int& v1, int& v2);
int index_of_smallest(const int a[], int start_index, int number_used);
void count_array(int sample_array[], int counter[], int number_used);
int count = 0;
int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 int sample_array[100], number_used;
 int counter[100] = {0};
 fill_array(sample_array, 100, number_used);
 count_array(sample_array, counter, number_used);
 sort(sample_array, number_used);
 cout << "\n";
 cout << "\n";
 cout << "Numbers\t";
 cout << "Times" << endl;
 for (int index = 0; index < number_used; index++)
  {
   cout << sample_array[index] << "\t";
   cout << counter[index] << endl;
  }
 cout << endl;
 cout << "\n";
 cout << "You entered " << count << " numbers." << endl;
 return 0;
}
int fill_array(int a[], int size, int& number_used)
{
 cout << "Enter up to " << size << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  int next, index = 0;
  cin >> next;
  while ((next >= 0) && (index < size))
  {
   a[index] = next;
   index++;
   cin >> next;
   count++;
  
  }
  number_used = index;
  return count;
}
void sort(int a[], int number_used)
{
 int index_of_next_smallest;
 for (int index = 0; index < number_used - 1; index++)
 {
  index_of_next_smallest = index_of_smallest(a, index, number_used);
  swap_values(a[index], a[index_of_next_smallest]);
 }
}
void swap_values(int& v1, int& v2)
{
 int temp;
 temp = v1;
 v1 = v2;
 v2 = temp;
}

int index_of_smallest(const int a[], int start_index, int number_used)
{
 int min = a[start_index], 
  index_of_min = start_index;
 for (int index = start_index + 1; index < number_used; index++)
  if (a[index] < min)
  {
   min = a[index];
   index_of_min = index;
  }
 return index_of_min;
}
void count_array(int sample_array[], int counter[], int number_used)
{
 for(int index=0; index<number_used; index++)
 {
  for(int index2=0; index2<number_used; index2++)
  {
   if (sample_array[index]==sample_array[index2])
    counter[index]++;
  }
  
 }
 
}

[ft3ssgeek]

IMHO...it would be easier just to do it the way you're already doing...get the list filled, then sort it...think of it this way, you spend the time to get one list filled then call one function to sort the list...the other way, you would have to call the function to sort the list every time you added to it...it's simply not as efficient...

[WaltP]

RaCheer. please consider formatting your code better. You really need to indent so the code can be followed.

[thekashyap]

int counter[100] = {0};

>> Just curious, is it guaranteed that this will always initialize elements indexed 1 to 99 with 0 ?

IMHO...it would be easier just to do it the way you're already doing...get the list filled, then sort it...think of it this way, you spend the time to get one list filled then call one function to sort the list...the other way, you would have to call the function to sort the list every time you added to it...it's simply not as efficient...

I hope no one intended to say that to "keep the list sorted after every insert" you have to "call sort function after every insert". :eek:. One can always find out the "right slot" where a new element should be inserted before inserting it. Where right slot is the slot that will ensure list's sorting sequence doesn't change. (e.g. lower/upper_bound() functions)
Now even if we do it the right way, from efficiency point of view I won't fully agree. If the array is large enough it might be faster to insert in a sorted order, than insert all and then sort.
But then you really won't be thinking of using a simple single dimensional array, but some kinda complicated tree structure (or a linked list perhaps as a second choice).

[thekashyap]

And BTW, no one seems to have spoken abt count() and count_if()..
You can use them as well..

[ft3ssgeek]

Well....because the OP is obviously new to C++ I was talking in terms that they would understand...So, if you want to ensure the list is sorted correctly after each input, you will still have to run the sort function...if you 97th input is the lowest number, it will need to move all 96 values up one cell...and if the 98th input is even lower, it will need to move all 97 value up one cell...

[RaCheer]

Unfortunately, I think I glanced at my results too quickly and got excited. They actually still read out bogus occurences. For ex:

Numbers Times

3 3
3 1
3 3
6 3


I see that another poster questioned whether:

int counter[100] = {0};

will always initialize elements indexed 1 to 99 with 0.

What am I overlooking?

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void sort(int a[], int number_used);
void swap_values(int& v1, int& v2);
int index_of_smallest(const int a[], int start_index, int number_used);
void count_array(int sample_array[], int counter[], int number_used);
int count = 0;
int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 int sample_array[100], number_used;
 int counter[100] = {0};
 fill_array(sample_array, 100, number_used);
 count_array(sample_array, counter, number_used);
 sort(sample_array, number_used);
 cout << "\n";
 cout << "\n";
 cout << "Numbers\t";
 cout << "Times" << endl;
 for (int index = 0; index < number_used; index++)
  {
   cout << sample_array[index] << "\t";
   cout << counter[index] << endl;
  }
 cout << endl;
 cout << "\n";
 cout << "You entered " << count << " numbers." << endl;
 return 0;
}
int fill_array(int a[], int size, int& number_used)
{
 cout << "Enter up to " << size << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  int next, index = 0;
  cin >> next;
  while ((next >= 0) && (index < size))
  {
   a[index] = next;
   index++;
   cin >> next;
   count++;
  
  }
  number_used = index;
  return count;
}
void sort(int a[], int number_used)
{
 int index_of_next_smallest;
 for (int index = 0; index < number_used - 1; index++)
 {
  index_of_next_smallest = index_of_smallest(a, index, number_used);
  swap_values(a[index], a[index_of_next_smallest]);
 }
}
void swap_values(int& v1, int& v2)
{
 int temp;
 temp = v1;
 v1 = v2;
 v2 = temp;
}

int index_of_smallest(const int a[], int start_index, int number_used)
{
 int min = a[start_index], 
  index_of_min = start_index;
 for (int index = start_index + 1; index < number_used; index++)
  if (a[index] < min)
  {
   min = a[index];
   index_of_min = index;
  }
 return index_of_min;
}
void count_array(int sample_array[], int counter[], int number_used)
{
 for(int index=0; index<number_used; index++)
 {
  for(int index2=0; index2<number_used; index2++)
  {
   if (sample_array[index]==sample_array[index2])
    counter[index]++;
  }
  
 }
 
}

Also, I found a code snippet that I might play with to work on an insertion sort. But I am still having trouble displaying which number(s) occur most often. I'm thinking an if-statement might work but I really have no clue. I don't know if I need to make another array or not. Thanks, guys. Ya'll have been so helpful!

[RaCheer]

This is odd. I was playing with an insertion sort, which still doesn't work, and now the occurence count result is correct. Could someone take a look at my code and see what I could do to make the isertion sort work correctly. In the results I get a jumble of numbers and letters, but I also get the correct number of times the numbers I entered occured. I'm so frustrated with this mess! THANK YOU!

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void insertion_sort(int sample_array[], int size, int number_used);
void count_array(int sample_array[], int counter[], int number_used);
int count = 0;
int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 int sample_array[100], number_used;
 int counter[100] = {0};
 fill_array(sample_array, 100, number_used);
 count_array(sample_array, counter, number_used);
 insertion_sort(sample_array, 100, number_used);
 cout << "\n";
 cout << "\n";
 cout << "Numbers\t";
 cout << "Times" << endl;
 for (int index = 0; index < number_used; index++)
  {
   cout << sample_array << "\t";
   cout << counter[index] << endl;
  }
 cout << endl;
 cout << "\n";
 cout << "You entered " << count << " numbers." << endl;
 return 0;
}
int fill_array(int a[], int size, int& number_used)
{
 cout << "Enter up to " << size << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  int next, index = 0;
  cin >> next;
  while ((next >= 0) && (index < size))
  {
   a[index] = next;
   index++;
   cin >> next;
   count++;
  
  }
  number_used = index;
  return count;
}
void insertion_sort(int sample_array[], int size, int number_used)
{
 int key, i;
 for (int number_used=1; number_used<size; number_used++)
 {
  key=sample_array[number_used];
  i=number_used-1;
  while(sample_array[i]>key && i>=0)
  {
    sample_array[i+1]=sample_array[i];
   i--;
  }
  sample_array[i+1]=key;
 }
 
}

void count_array(int sample_array[], int counter[], int number_used)
{
 for(int index=0; index<number_used; index++)
 {
  for(int index2=0; index2<number_used; index2++)
  {
   if (sample_array[index]==sample_array[index2])
    counter[index]++;
  }
  
 }
 
}