C++ RSS C++ RSS

Insertion Sort and Number Occurence

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Feb 2007
Posts: 31
Reputation: RaCheer is an unknown quantity at this point 
Solved Threads: 0
RaCheer RaCheer is offline Offline
Light Poster

Insertion Sort and Number Occurence

 
0
  #1
Apr 1st, 2007
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:

C++ Syntax (Toggle Plain Text) 
  1.  
  2.  
  3. #include <iostream>
  4. using namespace std;
  5. int fill_array(int a[], int size, int& number_used);
  6. void insertion_sort(int sample_array[], int size, int number_used);
  7. void count_array(int sample_array[], int counter[], int number_used);
  8. int count = 0;
  9. int main()
  10. {
  11.  
  12. cout << "This program sorts numbers from lowest to highest.\n";
  13. int sample_array[100], number_used;
  14. int counter[100] = {0};
  15. fill_array(sample_array, 100, number_used);
  16. count_array(sample_array, counter, number_used);
  17. insertion_sort(sample_array, 100, number_used);
  18. cout << "\n";
  19. cout << "\n";
  20. cout << "Numbers\t";
  21. cout << "Times" << endl;
  22. for (int index = 0; index < number_used; index++)
  23.   {
  24.    cout << sample_array << "\t";
  25.    cout << counter[index] << endl;
  26.   }
  27. cout << endl;
  28. cout << "\n";
  29. cout << "You entered " << count << " numbers." << endl;
  30. return 0;
  31. }
  32. int fill_array(int a[], int size, int& number_used)
  33. {
  34. cout << "Enter up to " << size << " nonnegative whole numbers.\n"
  35.    << "Mark the end of the list with a negative number.\n";
  36.   int next, index = 0;
  37.   cin >> next;
  38.   while ((next >= 0) && (index < size))
  39.   {
  40.    a[index] = next;
  41.    index++;
  42.    cin >> next;
  43.    count++;
  44.  
  45.   }
  46.   number_used = index;
  47.   return count;
  48. }
  49. void insertion_sort(int sample_array[], int size, int number_used)
  50. {
  51. int key, i;
  52. for (int number_used=1; number_used<size; number_used++)
  53. {
  54.   key=sample_array[number_used];
  55.   i=number_used-1;
  56.   while(sample_array[i]>key && i>=0)
  57.   {
  58.     sample_array[i+1]=sample_array[i];
  59.    i--;
  60.   }
  61.   sample_array[i+1]=key;
  62. }
  63.  
  64. }
  65.  
  66. void count_array(int sample_array[], int counter[], int number_used)
  67. {
  68. for(int index=0; index<number_used; index++)
  69. {
  70.   for(int index2=0; index2<number_used; index2++)
  71.   {
  72.    if (sample_array[index]==sample_array[index2])
  73.     counter[index]++;
  74.   }
  75.  
  76. }
  77.  
  78. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Insertion Sort and Number Occurence

 
0
  #2
Apr 1st, 2007
>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.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2005
Posts: 1,676
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is offline Offline
Posting Virtuoso

Re: Insertion Sort and Number Occurence

 
0
  #3
Apr 1st, 2007
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2007
Posts: 31
Reputation: RaCheer is an unknown quantity at this point 
Solved Threads: 0
RaCheer RaCheer is offline Offline
Light Poster

Re: Insertion Sort and Number Occurence

 
0
  #4
Apr 1st, 2007
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!

C++ Syntax (Toggle Plain Text) 
  1.  
  2. #include <iostream>
  3. using namespace std;
  4. int fill_array(int a[], int size, int& number_used);
  5. void insertion_sort(int sample_array[], int size, int key, int number_used);
  6. void count_array(int sample_array[], int counter[], int number_used);
  7. int count = 0;
  8. int main()
  9. {
  10.  
  11.  cout << "This program sorts numbers from lowest to highest.\n";
  12.  
  13.  int key = 0;
  14.  int sample_array[100], number_used;
  15.  int counter[100] = {0};
  16.  fill_array(sample_array, 100, number_used);
  17.  count_array(sample_array, counter, number_used);
  18.  insertion_sort(sample_array, 100, key, number_used);
  19.  cout << "\n";
  20.  cout << "\n";
  21.  cout << "Numbers\t";
  22.  cout << "Times" << endl;
  23.  for (int index = 0; index < number_used; index++)
  24.   {
  25.    cout << sample_array[index] << "\t";
  26.    cout << counter[index] << endl;
  27.   }
  28.  cout << endl;
  29.  cout << "\n";
  30.  cout << "You entered " << count << " numbers." << endl;
  31.  return 0;
  32. }
  33. int fill_array(int a[], int size, int& number_used)
  34. {
  35.  cout << "Enter up to " << size << " nonnegative whole numbers.\n"
  36.    << "Mark the end of the list with a negative number.\n";
  37.   int next, index = 0;
  38.   cin >> next;
  39.   while ((next >= 0) && (index < size))
  40.   {
  41.    a[index] = next;
  42.    index++;
  43.    cin >> next;
  44.    count++;
  45.  
  46.   }
  47.   number_used = index;
  48.   return count;
  49. }
  50. void insertion_sort(int sample_array[], int size, int key, int number_used)
  51. {
  52.  int i;
  53.  for (int number_used=1; number_used<size; number_used++)
  54.  {
  55.   key=sample_array[number_used];
  56.   i=number_used-1;
  57.   while(sample_array[i]>key && i>=0)
  58.   {
  59.     sample_array[i+1]=sample_array[i];
  60.    i--;
  61.   }
  62.   sample_array[i+1]=key;
  63.  }
  64.  
  65. }
  66.  
  67. void count_array(int sample_array[], int counter[], int number_used)
  68. {
  69.  for(int index=0; index<number_used; index++)
  70.  {
  71.   for(int index2=0; index2<number_used; index2++)
  72.   {
  73.    if (sample_array[index]==sample_array[index2])
  74.     counter[index]++;
  75.   }
  76.  
  77.  }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2005
Posts: 1,676
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is offline Offline
Posting Virtuoso

Re: Insertion Sort and Number Occurence

 
0
  #5
Apr 1st, 2007
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.

C++ Syntax (Toggle Plain Text) 
  1. void insertion_sort(int * sample_array, int number_used, int valueToEnter)
  2. {
  3.    int i = 0;
  4.  
  5.    //find insertion point
  6.    while(i < number_used && sample_array[i] < valueToEnter)      
  7.        ++i;
  8.  
  9.    //shift all elements from insertion point to end of array to right by 1.
  10.    if(number_used > 0)
  11.    {
  12.      for(int w = number_used - 1; w >= i ; --w)
  13.         sample_array[w + 1] = sample_array[w];
  14.    }
  15.  
  16.   //insert valueToEnter at index i
  17.   sample_array[i] = valueToEnter;
  18. }
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2007
Posts: 31
Reputation: RaCheer is an unknown quantity at this point 
Solved Threads: 0
RaCheer RaCheer is offline Offline
Light Poster

Re: Insertion Sort and Number Occurence

 
0
  #6
Apr 1st, 2007
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!

C++ Syntax (Toggle Plain Text) 
  1.  
  2. #include <iostream>
  3. using namespace std;
  4. int fill_array(int a[], int size, int& number_used);
  5. void insertion_sort(int * sample_array, int number_used, int valueToEnter);
  6. void count_array(int sample_array[], int counter[], int number_used);
  7. int count = 0;
  8. int main()
  9. {
  10.  
  11.  cout << "This program sorts numbers from lowest to highest.\n";
  12.  
  13.  int valueToEnter = 0;
  14.  int sample_array[100], number_used;
  15.  int counter[100] = {0};
  16.  fill_array(sample_array, 100, number_used);
  17.  count_array(sample_array, counter, number_used);
  18.  insertion_sort(sample_array, number_used, valueToEnter);
  19.  cout << "\n";
  20.  cout << "\n";
  21.  cout << "Numbers\t";
  22.  cout << "Times" << endl;
  23.  for (int index = 0; index < number_used; index++)
  24.   {
  25.    cout << sample_array[index] << "\t";
  26.    cout << counter[index] << endl;
  27.   }
  28.  cout << endl;
  29.  cout << "\n";
  30.  cout << "You entered " << count << " numbers." << endl;
  31.  return 0;
  32. }
  33. int fill_array(int a[], int size, int& number_used)
  34. {
  35.  cout << "Enter up to " << size << " nonnegative whole numbers.\n"
  36.    << "Mark the end of the list with a negative number.\n";
  37.   int next, index = 0;
  38.   cin >> next;
  39.   while ((next >= 0) && (index < size))
  40.   {
  41.    a[index] = next;
  42.    index++;
  43.    cin >> next;
  44.    count++;
  45.  
  46.   }
  47.   number_used = index;
  48.   return count;
  49. }
  50. void insertion_sort(int * sample_array, int number_used, int valueToEnter)
  51. {
  52.  int i =0;
  53.  while(i < number_used && sample_array[i] < valueToEnter)
  54.   i++;
  55.  if(number_used > 0)
  56.  {
  57.   for(int w = number_used - 1; w >= i; --w)
  58.    sample_array[w + 1] = sample_array[w];
  59.  }
  60.  sample_array[i] = valueToEnter;
  61.  
  62. }
  63.  
  64. void count_array(int sample_array[], int counter[], int number_used)
  65. {
  66.  for(int index=0; index<number_used; index++)
  67.  {
  68.   for(int index2=0; index2<number_used; index2++)
  69.   {
  70.    if (sample_array[index]==sample_array[index2])
  71.     counter[index]++;
  72.   }
  73.  
  74.  }
  75.  
  76. }
Last edited by RaCheer; Apr 1st, 2007 at 4:06 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2005
Posts: 1,676
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is offline Offline
Posting Virtuoso

Re: Insertion Sort and Number Occurence

 
0
  #7
Apr 1st, 2007
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.
C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void fill_array(int a[], int, int& );
  5. void insertion_sort(int *, int, int);
  6.  
  7. int main()
  8. {
  9.  const int SIZE = 100;
  10.  int sample_array[SIZE];
  11.  int number_used = 0;
  12.  
  13.  cout << "This program sorts numbers from lowest to highest.\n";
  14.  
  15.  fill_array(sample_array, SIZE, number_used);
  16.  
  17.  return 0;
  18. }
  19.  
  20. void fill_array(int a[], const int SIZE, int& number_used)
  21. {
  22.  int next = 1;
  23.  cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
  24.    << "Mark the end of the list with a negative number.\n";
  25.  
  26.   while(number_used < SIZE && next > 0)
  27.   {
  28.     cin >> next;
  29.     if(next >= 0)
  30.     {
  31.       insertion_sort(sample_array, number_used, next);
  32.       ++number_used;
  33.     }
  34.   }
  35. }
  36.  
  37. void insertion_sort(int * sample_array, int number_used, int valueToEnter)
  38. {
  39.  int i =0;
  40.  while(i < number_used && sample_array[i] < valueToEnter)
  41.   i++;
  42.  if(number_used > 0)
  43.  {
  44.   for(int w = number_used - 1; w >= i; --w)
  45.    sample_array[w + 1] = sample_array[w];
  46.  }
  47.  sample_array[i] = valueToEnter; 
  48. }
WARNING--code not vetted
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2007
Posts: 31
Reputation: RaCheer is an unknown quantity at this point 
Solved Threads: 0
RaCheer RaCheer is offline Offline
Light Poster

Re: Insertion Sort and Number Occurence

 
0
  #8
Apr 1st, 2007
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.

C++ Syntax (Toggle Plain Text) 
  1.  
  2. #include <iostream>
  3. using namespace std;
  4. int fill_array(int a[], int, int& );
  5. void insertion_sort(int *, int, int);
  6. void count_array(int sample_array[], int counter[], int number_used);
  7. int count = 0;
  8. int main()
  9. {
  10.  
  11.  cout << "This program sorts numbers from lowest to highest.\n";
  12.  
  13.  const int SIZE = 100;
  14.  int sample_array[SIZE];
  15.  int number_used =0;
  16.  int counter[100] = {0};
  17.  fill_array(sample_array, SIZE, number_used);
  18.  count_array(sample_array, counter, number_used);
  19.  cout << "\n";
  20.  cout << "\n";
  21.  cout << "Numbers\t";
  22.  cout << "Times" << endl;
  23.  for (int index = 0; index < number_used; index++)
  24.   {
  25.    cout << sample_array[index] << "\t";
  26.    cout << counter[index] << endl;
  27.   }
  28.  cout << endl;
  29.  cout << "\n";
  30.  cout << "You entered " << count << " numbers." << endl;
  31.  return 0;
  32. }
  33. int fill_array(int sample_array[], const int SIZE, int& number_used)
  34. {
  35.  
  36.   int next =1;
  37.   cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
  38.    << "Mark the end of the list with a negative number.\n";
  39.  
  40.   while (number_used < SIZE && next > 0)
  41.   {
  42.    cin >> next;
  43.    if (next >=0)
  44.    {
  45.     insertion_sort(sample_array, number_used, next);
  46.     ++number_used;
  47.     count++;
  48.    }
  49.   }
  50.   return count;
  51.  }
  52.  
  53.  
  54.  
  55. void insertion_sort(int * sample_array, int number_used, int valueToEnter)
  56. {
  57.  int i =0;
  58.  while(i < number_used && sample_array[i] < valueToEnter)
  59.   i++;
  60.  if(number_used > 0)
  61.  {
  62.   for(int w = number_used - 1; w >= i; --w)
  63.    sample_array[w + 1] = sample_array[w];
  64.  }
  65.  sample_array[i] = valueToEnter;
  66.  
  67. }
  68.  
  69. void count_array(int sample_array[], int counter[], int number_used)
  70. {
  71.  for(int index=0; index<number_used; index++)
  72.  {
  73.   for(int index2=0; index2<number_used; index2++)
  74.   {
  75.    if (sample_array[index]==sample_array[index2])
  76.     counter[index]++;
  77.   }
  78.  
  79.  }
  80.  
  81. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Feb 2007
Posts: 31
Reputation: RaCheer is an unknown quantity at this point 
Solved Threads: 0
RaCheer RaCheer is offline Offline
Light Poster

Re: Insertion Sort and Number Occurence

 
0
  #9
Apr 1st, 2007
Could someone please assist me with my previous question? Thank you!
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2005
Posts: 1,676
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is offline Offline
Posting Virtuoso

Re: Insertion Sort and Number Occurence

 
0
  #10
Apr 1st, 2007
>>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[i] is the same value as valueToEnter. If it is, then you increase the value of counter[i] 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.

C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int fill_array(int a[], int *, const int)
  5. void insertion_sort(int *, int*, int&, int);
  6.  
  7. int main()
  8. {
  9.  
  10.  cout << "This program sorts numbers from lowest to highest.\n";
  11.  
  12.  const int SIZE = 100;
  13.  int sample_array[SIZE];
  14.  int count = 0; //to keep track of total numbers user enters
  15.  int counter[SIZE] = {0};
  16.  
  17.  
  18.  count = fill_array(sample_array, counter, SIZE,  number_used);
  19.  
  20.  cout << "\n";
  21.  cout << "\n";
  22.  
  23.  cout << "You entered " << count << " numbers." << endl;
  24.  
  25.  //find max frequency value in counter here
  26.  
  27.  //search counter for all elements have max frequency value here
  28.    //if current element of counter has max value 
  29.       //print out sample_array[x] and counter[x];
  30.  
  31.  return 0;
  32. }
  33.  
  34. int fill_array(int sample_array[], int * counter, const int SIZE)
  35. {
  36.   int count = 0;
  37.   int next = 1;
  38.   int number_used = 0; //to keep track of unique numbers entered by user
  39.   cout << "Enter up to " << SIZE << " nonnegative whole numbers.\n"
  40.    << "Mark the end of the list with a negative number.\n";
  41.  
  42.   //user can input up to SIZE (set at 100 now) numbers 
  43.   while (count < SIZE && next > 0)
  44.   {
  45.     cin >> next;
  46.     if (next >=0)
  47.     {
  48.       insertion_sort(sample_array, counter, number_used, next);
  49.       count++;
  50.       //Note: if duplicate numbers entered number_used will be less than count
  51.    }
  52.   }
  53.   return count;
  54. }
  55.  
  56.  
  57. void insertion_sort(int * sample_array, int * counter, int & number_used, int valueToEnter)
  58. {
  59.  int i =0;
  60.  
  61.  while(i < number_used && sample_array[i] < valueToEnter)
  62.   i++;
  63.  
  64.  if(number_used == 0) 
  65.  //means this is the first value entered into sample_array
  66.  {
  67.    sample_array[0] = valueToEnter;
  68.    //increment counter[0] to 1;
  69.    //increment number_used by one;
  70.  }
  71.  else  
  72.  //means this is not the first value entered into sample_arrray
  73.  {
  74.    if //sample_array[i] is equal to valueToEnter
  75.      //increment counter[i];
  76.    else 
  77.    { 
  78.      //means sample_array[i] not equal to valueToEnter 
  79.      //which also means valueToEnter is unique so far  
  80.      //shift all items at index i and beyond in sample_array and 
  81.      //counter to the right by one
  82.      for(int w = number_used - 1; w >= i; --w)
  83.      {
  84.        sample_array[w + 1] = sample_array[w];
  85.        //do the same in counter here
  86.      }
  87.  
  88.       //enter valueToEnter at sample_array[i];
  89.       sample_array[i] = valueToEnter;
  90.  
  91.       //set counter[i] to value of 1 since we know it is unique
  92.  
  93.       //increment number_used by one;
  94.     }
  95.   }
  96. }
Last edited by Lerner; Apr 1st, 2007 at 11:27 pm.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based beginner binary bitmap c++ c/c++ calculator char char* class code coding compile compiler console conversion count database delete deploy developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int java lib linkedlist linker list loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference rpg sorting string strings temperature template test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC