--------------------
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:

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?

Mayank SAssociate Director - Product EngineeringCommented:

Hi Ben,

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.

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

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.

0

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Mayank SAssociate Director - Product EngineeringCommented:

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 SAssociate Director - Product EngineeringCommented:

>> 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.

0

killer455Author Commented:

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?

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

0

Featured Post

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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.