killer455
asked on
Class, Array Sort on Insert - EASY - help :)
--------------------
Program Description
--------------------
This is a lottery program. Five numbers are inputed from the user into an array. The array is then sorted. This list, the first list, is considered the "winning numbers" list.
A file containing sets of 5 numbers on a line... ex:
numbers1.txt
1 2 3 4 5
23 32 34 45 34
4 9 10 18 7
... etc.
A set of five numbers (one line) is taken in from the file a set at a time, put into an array, and then sorted. The array is then compared to the "winning list" mentioned above. If the arrays are identical a counter is incremented by 1, indicating a match or a "win". This is done for every line in the file until the end of the file.
------------------
Problem/Questions
------------------
1) Is there a better way to sort these arrays? I'm hoping to be able to sort them on input, or in other words when they are being added to the array. (instead of doing a seperate method). This needs to work for the second array though. The second array is filled once, then cleared, filled, cleared... and so on and am not sure it will work. But let me know please.
2) These sorted lists are implemented as arrays, can they be implemented as a linked list... any tips in this area?
Thanks.
------------------
Code
------------------
-----------------
lottery.h
-----------------
#ifndef LOTTERY_H
#define LOTTERY_H
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void SortList();
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
int count;
int winner;
int arr[5];
};
#endif
---------------
lottery.cpp
---------------
#include "lottery.h"
Lottery::Lottery()
{
count=0;
winner=0;
}
bool Lottery::AddNumber(int number)
{
if(count<5){
arr[count++]=number; return true;
}
return false;
}
void Lottery::Clear()
{
count=0;
}
bool Lottery::isFull()
{
if(count==5)
{
return true;
}
return false;
}
void Lottery::SortList()
{
for(int i=1, j; i<5; i++)
{
int tmp=arr[i];
for(j=i-1; j>=0 && arr[j]>tmp; j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=tmp;
}
}
bool Lottery::CompareLists(Lott
{
for(int i=0; (i<count) && (i<lot2.count); i++)
{
if(arr[i]!=lot2.arr[i])
{
return 0;
}
}
return 1;
}
-------------------
lotterycheck.cpp
-------------------
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "lottery.h"
int main()
{
int winner=0;
int winNum=0;
int winPosition=0;
Lottery list1, list2;
cout << "Enter the winning numbers: ";
while(winPosition<5)
{
cin >> winNum;
list1.AddNumber(winNum);
winPosition++;
}
list1.SortList();
ifstream fileInput;
string inData;
cout << "input file: ";
cin >> inData;
fileInput.open(inData.c_st
int number;
while(fileInput >> number)
{
list2.AddNumber(number);
if(list2.isFull())
{
list2.SortList();
if(list1.CompareLists(list
{ winner ++; }
list2.Clear();
}
}
cout << winner << endl;
return 0;
}
Thanks
Ben
Program Description
--------------------
This is a lottery program. Five numbers are inputed from the user into an array. The array is then sorted. This list, the first list, is considered the "winning numbers" list.
A file containing sets of 5 numbers on a line... ex:
numbers1.txt
1 2 3 4 5
23 32 34 45 34
4 9 10 18 7
... etc.
A set of five numbers (one line) is taken in from the file a set at a time, put into an array, and then sorted. The array is then compared to the "winning list" mentioned above. If the arrays are identical a counter is incremented by 1, indicating a match or a "win". This is done for every line in the file until the end of the file.
------------------
Problem/Questions
------------------
1) Is there a better way to sort these arrays? I'm hoping to be able to sort them on input, or in other words when they are being added to the array. (instead of doing a seperate method). This needs to work for the second array though. The second array is filled once, then cleared, filled, cleared... and so on and am not sure it will work. But let me know please.
2) These sorted lists are implemented as arrays, can they be implemented as a linked list... any tips in this area?
Thanks.
------------------
Code
------------------
-----------------
lottery.h
-----------------
#ifndef LOTTERY_H
#define LOTTERY_H
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void SortList();
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
int count;
int winner;
int arr[5];
};
#endif
---------------
lottery.cpp
---------------
#include "lottery.h"
Lottery::Lottery()
{
count=0;
winner=0;
}
bool Lottery::AddNumber(int number)
{
if(count<5){
arr[count++]=number; return true;
}
return false;
}
void Lottery::Clear()
{
count=0;
}
bool Lottery::isFull()
{
if(count==5)
{
return true;
}
return false;
}
void Lottery::SortList()
{
for(int i=1, j; i<5; i++)
{
int tmp=arr[i];
for(j=i-1; j>=0 && arr[j]>tmp; j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=tmp;
}
}
bool Lottery::CompareLists(Lott
{
for(int i=0; (i<count) && (i<lot2.count); i++)
{
if(arr[i]!=lot2.arr[i])
{
return 0;
}
}
return 1;
}
-------------------
lotterycheck.cpp
-------------------
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "lottery.h"
int main()
{
int winner=0;
int winNum=0;
int winPosition=0;
Lottery list1, list2;
cout << "Enter the winning numbers: ";
while(winPosition<5)
{
cin >> winNum;
list1.AddNumber(winNum);
winPosition++;
}
list1.SortList();
ifstream fileInput;
string inData;
cout << "input file: ";
cin >> inData;
fileInput.open(inData.c_st
int number;
while(fileInput >> number)
{
list2.AddNumber(number);
if(list2.isFull())
{
list2.SortList();
if(list1.CompareLists(list
{ winner ++; }
list2.Clear();
}
}
cout << winner << endl;
return 0;
}
Thanks
Ben
For small lists bubblesort and insertion sort are better performers (not that it matters with a small list)
a very simple way of sorting this type of stuff is just this
//just a simple insertion sort
//this assumes the the array arr is already sorted
bool Lottery::AddNumber(int number)
{
if(count >= 5)
return false;
for(int i =count; i>0; i--){
if(number > arr[i-1]){
break;
}
else //here is where link lists will help
arr[i] = arr[i-1];
}
arr[i] = number;
count++;
return true;
}
in both of these cases you don't have to sort afterward.. we do it on insertion
a very simple way of sorting this type of stuff is just this
//just a simple insertion sort
//this assumes the the array arr is already sorted
bool Lottery::AddNumber(int number)
{
if(count >= 5)
return false;
for(int i =count; i>0; i--){
if(number > arr[i-1]){
break;
}
else //here is where link lists will help
arr[i] = arr[i-1];
}
arr[i] = number;
count++;
return true;
}
in both of these cases you don't have to sort afterward.. we do it on insertion
Linked lists will provide more flexibility, and they are not restricted to size like your array.
struct list
{
int data ;
list * next ;
} ; // structure-definition over
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void SortList();
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
list * first ;
}; // class definition over
Lottery :: Lottery ()
{
first = NULL ; // include one of stdlib or stddef or stdio or malloc, etc (for NULL)
}
void Lottery :: AddNumber (int number)
{
list * ptr = new list ;
ptr -> data = number ;
ptr -> next = NULL ;
if ( first == NULL )
first = ptr ; // end if
else
{
for ( list * temp = ptr ; temp -> next != NULL ; temp = temp -> next )
; // end for
temp -> next = ptr ;
} // end else
} // end of AddNumber ()
If you want, then you can also check if there is enough memory before allocating and accordingly return true or false from thsi function, but I have ignored that part (so I've also given 'void' as the return type).
I hope you can try to write the other functions on your own.
Hope that helps!
Mayank.
struct list
{
int data ;
list * next ;
} ; // structure-definition over
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void SortList();
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
list * first ;
}; // class definition over
Lottery :: Lottery ()
{
first = NULL ; // include one of stdlib or stddef or stdio or malloc, etc (for NULL)
}
void Lottery :: AddNumber (int number)
{
list * ptr = new list ;
ptr -> data = number ;
ptr -> next = NULL ;
if ( first == NULL )
first = ptr ; // end if
else
{
for ( list * temp = ptr ; temp -> next != NULL ; temp = temp -> next )
; // end for
temp -> next = ptr ;
} // end else
} // end of AddNumber ()
If you want, then you can also check if there is enough memory before allocating and accordingly return true or false from thsi function, but I have ignored that part (so I've also given 'void' as the return type).
I hope you can try to write the other functions on your own.
Hope that helps!
Mayank.
Referring to my previous comment: Of course, you will also have to change the return-type of the AddNumber () function in its declaration inside the class from 'bool' to 'void' if that is the definition that you provide for it.
Mayank.
Mayank.
The above only adds to the end of the list not sorted....
but this allows sorting on insertion with linked lists
struct node{
int number;
struct node * next;
node(int num):number(num), next(NULL){}
};
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
int count;
int winner;
node * list;
};
//similar
Lottery :: Lottery ():list(NULL), count(0), winner(0)
{
}
void Lottery::AddNumber(int number)
{
count++;
node * newnode = new node(number);
node * temp;
if(!list || number < list->number)
{
temp = list;
list = newnode;
newnode->next = temp;
return;
}
for(temp = list; temp->next; temp=temp->next)
{
if(number < temp->next->number)
break;
}
node * tempNext=temp->next;
temp->next = newnode;
newnode->next = tempNext;
return;
}
but this allows sorting on insertion with linked lists
struct node{
int number;
struct node * next;
node(int num):number(num), next(NULL){}
};
class Lottery
{
public:
Lottery();
bool AddNumber(int number);
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);
private:
int count;
int winner;
node * list;
};
//similar
Lottery :: Lottery ():list(NULL), count(0), winner(0)
{
}
void Lottery::AddNumber(int number)
{
count++;
node * newnode = new node(number);
node * temp;
if(!list || number < list->number)
{
temp = list;
list = newnode;
newnode->next = temp;
return;
}
for(temp = list; temp->next; temp=temp->next)
{
if(number < temp->next->number)
break;
}
node * tempNext=temp->next;
temp->next = newnode;
newnode->next = tempNext;
return;
}
>> The above only adds to the end of the list not sorted
Agreed. He has a different function for sorting and I asked him to try and write out the other functions himself.
Mayank.
Agreed. He has a different function for sorting and I asked him to try and write out the other functions himself.
Mayank.
ASKER
Nice responses guy's. They are helping a lot. I am still working on moving this program over to a linked list implementation. The reason I did it with an array in the first place is that I was more familiar with them. I am still learning linked lists.
Is there a way, with the array implementation, to sort on insertion? In other words get rid of the sort method and just have it sort correctly on the AddNumber method? The only problem I saw in this is I am using the same array several times, loading, and reloading the list and i didnt know if this would effect it.
Frogger1999 provided a bubble sort but the array must already be sorted. Well I am adding numbers to am empty array and hoping to sort them on insertion, and then compare to the other array accordingly. Then clear the list, and perform the same action over again, and compare again.... and so on. So I dont think your bubble sort will work will it?
Thanks
Ben
Is there a way, with the array implementation, to sort on insertion? In other words get rid of the sort method and just have it sort correctly on the AddNumber method? The only problem I saw in this is I am using the same array several times, loading, and reloading the list and i didnt know if this would effect it.
Frogger1999 provided a bubble sort but the array must already be sorted. Well I am adding numbers to am empty array and hoping to sort them on insertion, and then compare to the other array accordingly. Then clear the list, and perform the same action over again, and compare again.... and so on. So I dont think your bubble sort will work will it?
Thanks
Ben
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I think that my implementation will work ok as long as count is set correctly. Basically I was saying that the insertion would work iff the elements in the array (up to array[count-1]) were already in sorted order
example:
if you insert into this array
a = { 0, 1, 2, X, Y} count = 3 then the insertion will work
the value of X and Y don't matter
also if you clear your list (by just setting count to 0) the [array] implementation will work
but if you have an array
{0, 5, 1, X, Y} then the insertion will not be in the correct order
The linked list implementation is similar in restriction you must have the previously inserted nodes in sorted order or the insertion may not put your node in the correct place.
However, I do believe that either will work, assuming you only insert into the list via my implementation of AddNumber because those implementation satisy the restrictions above.
So basically my implementation assume that you can start from a cleared array (count == 0) or from a partially sorted array (first count items sorted)
and for the linked list implementation you can start from a cleared list (list == NULL) or an already sorted list (all nodes in sorted order) assuming that you always insert with AddNumber (or some other way that guarantees sortedness)
hth
example:
if you insert into this array
a = { 0, 1, 2, X, Y} count = 3 then the insertion will work
the value of X and Y don't matter
also if you clear your list (by just setting count to 0) the [array] implementation will work
but if you have an array
{0, 5, 1, X, Y} then the insertion will not be in the correct order
The linked list implementation is similar in restriction you must have the previously inserted nodes in sorted order or the insertion may not put your node in the correct place.
However, I do believe that either will work, assuming you only insert into the list via my implementation of AddNumber because those implementation satisy the restrictions above.
So basically my implementation assume that you can start from a cleared array (count == 0) or from a partially sorted array (first count items sorted)
and for the linked list implementation you can start from a cleared list (list == NULL) or an already sorted list (all nodes in sorted order) assuming that you always insert with AddNumber (or some other way that guarantees sortedness)
hth
In your code, you are only sorting the second list after filling it entirely to its limit, so I guess you are not performing the sorting right during insertion, but after all of them are inserted.
As for technique, there are so many of them - you can try heap-sort (O(n log n). Its my personal favourite. Quick-sort also has O(n log n) but in case the original array is already sorted, then it becomes the wort-case for it, with an order of n*n.
You also asked about linked lists. They can definitely be implemented in your program.
In your SorList () function, it is better to write:
for(int i=1, j; i<count; i++) // 'count' instead of 5
Also, you can remove the 'winner' member altogether from the class as I don't think that you're using it anywhere in hte functions of that class. You already have a different 'winner' in main (), which you are using there.
Mayank.