Insertion Sort and Number Occurence

[RaCheer]

Hello! I have written a program that lets the user enter numbers and they are then sorted into ascending order. The number of times each number occurs is also displayed. I previously wrote it using a selection sort but could not get the times each number occured to display correctly. Now I have tried to write it using an insertion sort. The number occurences display correctly now, however, I can't get the list of numbers to display right. I get a bunch of random numbers and letters. If someone could help me tidy up my code I'd greatly appreciate it.

Also, I would like to display the number(s) that occur most often. Say for ex: I enter 6 3 6 3 5. Both 6 and 3 would would be displayed. How would I go about doing this? Thank you! :cheesy:

I have included my code as follows:

#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]++;
  }
  
}

}

>Say for ex: I enter 6 3 6 3 5. Both 6 and 3 would would be displayed. How would I go about doing this?

Set up a frequency count for each number.

[Lerner]

A map would be one way to do it. If you don't know about maps, then using a sequence of arrays can do it, too.

After your initial array is sorted it will look like this:
A => 33566
Now you could set up an array of unique numbers in the array which could look like this:
B => 356
and a separate array of frequencies for each of those numbers which would look like this:
C => 212
Then you could sort the frequencies changing B and C at the same time so you end up with something like this:
B => 536
C => 122

If you don't want to change B and C you could always use new arrays to hold the unique values associated with any given frequency in the order of their frequency of occurrence.

[RaCheer]

Before I work on the number frequencies I need to get my insertion sort working and right now it doesn't.

If I enter:

9
1
3
3

I get this in the results for my sort:

Numbers

-858993460
-858993460
-858993460
-858993460

Right now I would be just as pleased if I could get this to work! 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 key, 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 key = 0;
 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, key, 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 insertion_sort(int sample_array[], int size, int key, int number_used)
{
 int 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]++;
  }
  
 }

[Lerner]

I think you are getting your variables mixed up. In fill_array() you assign the value of index to number_used which is passed to fill_array as a reference to an int so that value can be passed from main() to insertion_sort(), but then you assign 1 to number_used which overwrites the number you took pains to retrieve and pass to insertion_sort() in the first place. That in turn makes it difficult for me to follow your logic in insertion_sort().

Even more basic to me, however, is that insertion_sort() implies that you sort the values as they are inserted, not after the entire array has been entered.

void insertion_sort(int * sample_array, int number_used, int valueToEnter)
{
   int i = 0;

   //find insertion point
   while(i < number_used && sample_array[i] < valueToEnter)      
       ++i;
   
   //shift all elements from insertion point to end of array to right by 1.
   if(number_used > 0)
   {
     for(int w = number_used - 1; w >= i ; --w)
        sample_array[w + 1] = sample_array[w];
   }

  //insert valueToEnter at index i
  sample_array[i] = valueToEnter;
}

and I would keep track of number_used and max size of sample_array in main() to be sure I didn't enter too many items in sample_array(). WARNING--above code not vetted.

[RaCheer]

Ok...I changed up the insertion sort to mirror yours. My results aren't as yucky, but they're still not right.

If I enter:

5
6
9
9

I get this in the ordered results:

Numbers

0
5
6
9

I wasn't sure where to declare valueToEnter or what to initialize it to, so I put it in main and initalized it to 0. I think that's why I have a 0 in the results. Help!

#include <iostream>
using namespace std;
int fill_array(int a[], int size, int& number_used);
void insertion_sort(int * sample_array, int number_used, int valueToEnter);
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 valueToEnter = 0;
 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, number_used, valueToEnter);
 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 insertion_sort(int * sample_array, int number_used, int valueToEnter)
{
 int i =0;
 while(i < number_used && sample_array[i] < valueToEnter)
  i++;
 if(number_used > 0)
 {
  for(int w = number_used - 1; w >= i; --w)
   sample_array[w + 1] = sample_array[w];
 }
 sample_array[i] = valueToEnter;
 
}
 
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]++;
  }
 
 }
 
}

[Lerner]

I have taken everything out of your program except the fill_array and insertion_sort subroutines and changed a few things cosmetically to suit my sense of style. The major change from your last post has to do with the fill_array() function.

#include <iostream>
using namespace std;

void fill_array(int a[], int, int& );
void insertion_sort(int *, int, int);

int main()
{
 const int SIZE = 100;
 int sample_array[SIZE];
 int number_used = 0;
 
 cout << "This program sorts numbers from lowest to highest.\n";
 
 fill_array(sample_array, SIZE, number_used);

 return 0;
}

void fill_array(int a[], const int SIZE, int& number_used)
{
 int next = 1;
 cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";

  while(number_used < SIZE && next > 0)
  {
    cin >> next;
    if(next >= 0)
    {
      insertion_sort(sample_array, number_used, next);
      ++number_used;
    }
  }
}

void insertion_sort(int * sample_array, int number_used, int valueToEnter)
{
 int i =0;
 while(i < number_used && sample_array[i] < valueToEnter)
  i++;
 if(number_used > 0)
 {
  for(int w = number_used - 1; w >= i; --w)
   sample_array[w + 1] = sample_array[w];
 }
 sample_array[i] = valueToEnter; 
}

WARNING--code not vetted

[RaCheer]

Wonderful! I now have my code working! You have been so helpful! Is there another way I can display the numbers that occur the most without using a map or array? I haven't learned maps and I can't imagine being assigned something I haven't learned yet. Is there a function or an if-statement that coud accomplish this? We only need 2 arrays for this project, one for the numbers and one for the count.

#include <iostream>
using namespace std;
int fill_array(int a[], int, int& );
void insertion_sort(int *, int, int);
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";
 
 const int SIZE = 100;
 int sample_array[SIZE];
 int number_used =0;
 int counter[100] = {0};
 fill_array(sample_array, SIZE, number_used);
 count_array(sample_array, counter, 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 sample_array[], const int SIZE, int& number_used)
{
 
  int next =1;
  cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  
  while (number_used < SIZE && next > 0)
  {
   cin >> next;
   if (next >=0)
   {
    insertion_sort(sample_array, number_used, next);
    ++number_used;
    count++;
   }
  }
  return count;
 }
  
  

void insertion_sort(int * sample_array, int number_used, int valueToEnter)
{
 int i =0;
 while(i < number_used && sample_array[i] < valueToEnter)
  i++;
 if(number_used > 0)
 {
  for(int w = number_used - 1; w >= i; --w)
   sample_array[w + 1] = sample_array[w];
 }
 sample_array[i] = valueToEnter;
 
}

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]++;
  }
  
 }
 
}

[RaCheer]

Could someone please assist me with my previous question? Thank you!

[Lerner]

>>Is there another way I can display the numbers that occur the most without using a map or array?

Make sample_array() an array of unique values instead of an array of all values. (Note: you will need an input counter to make sure that total number of numbers entered by user doesn't exceed a given value if they are only allowed to enter a given number of inputs. In your code you are already doing this partway with count++) That is after you find the insertion point check to see if sample_array is the same value as valueToEnter. If it is, then you increase the value of counter by one but you don't insert valueToEnter into sample_array. If it isn't, then you insert the valueToEnter as before, but you must also shift the values of the elements in counter similarly. That is each counter[x] represents the number of times sample_array[x] is entered by the user.

When user input has been completed you can search the counter for the max frequency value. Then you can search counter for all the elements with the value of maximum frequency and output the elements in sample_array and counter whose index is associated with the maximum frequenct value.

In the following code I've changed the function prototypes slightly to accomodate passing counter back and forth. I've commented where I'd add things I talked about above, but I've not actually written all of the code. WARNING: I've not tested the code.

#include <iostream>
using namespace std;

int fill_array(int a[], int *, const int)
void insertion_sort(int *, int*, int&, int);

int main()
{
 
 cout << "This program sorts numbers from lowest to highest.\n";
 
 const int SIZE = 100;
 int sample_array[SIZE];
 int count = 0; //to keep track of total numbers user enters
 int counter[SIZE] = {0};
 

 count = fill_array(sample_array, counter, SIZE,  number_used);
 
 cout << "\n";
 cout << "\n";
 
 cout << "You entered " << count << " numbers." << endl;

 //find max frequency value in counter here
    
 //search counter for all elements have max frequency value here
   //if current element of counter has max value 
      //print out sample_array[x] and counter[x];

 return 0;
}

int fill_array(int sample_array[], int * counter, const int SIZE)
{
  int count = 0;
  int next = 1;
  int number_used = 0; //to keep track of unique numbers entered by user
  cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
   << "Mark the end of the list with a negative number.\n";
  
  //user can input up to SIZE (set at 100 now) numbers 
  while (count < SIZE && next > 0)
  {
    cin >> next;
    if (next >=0)
    {
      insertion_sort(sample_array, counter, number_used, next);
      count++;
      //Note: if duplicate numbers entered number_used will be less than count
   }
  }
  return count;
}
  
  
void insertion_sort(int * sample_array, int * counter, int & number_used, int valueToEnter)
{
 int i =0;

 while(i < number_used && sample_array[i] < valueToEnter)
  i++;

 if(number_used == 0) 
 //means this is the first value entered into sample_array
 {
   sample_array[0] = valueToEnter;
   //increment counter[0] to 1;
   //increment number_used by one;
 }
 else  
 //means this is not the first value entered into sample_arrray
 {
   if //sample_array[i] is equal to valueToEnter
     //increment counter[i];
   else 
   { 
     //means sample_array[i] not equal to valueToEnter 
     //which also means valueToEnter is unique so far  
     //shift all items at index i and beyond in sample_array and 
     //counter to the right by one
     for(int w = number_used - 1; w >= i; --w)
     {
       sample_array[w + 1] = sample_array[w];
       //do the same in counter here
     }

      //enter valueToEnter at sample_array[i];
      sample_array[i] = valueToEnter;

      //set counter[i] to value of 1 since we know it is unique

      //increment number_used by one;
    }
  }
}