Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 289

# 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();
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;
}

{
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(Lottery& lot2)
{
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;
winPosition++;
}

list1.SortList();

ifstream fileInput;
string inData;

cout << "input file: ";
cin >> inData;

fileInput.open(inData.c_str());
int number;

while(fileInput >> number)
{
if(list2.isFull())
{
list2.SortList();
if(list1.CompareLists(list2))
{ winner ++; }
list2.Clear();
}
}
cout << winner << endl;

return 0;
}

Thanks
Ben
0
killer455
• 5
• 3
1 Solution

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

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.

0

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

0

Associate Director - Product EngineeringCommented:
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();
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.
0

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

Commented:
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();
void Clear();
bool isFull();
bool CompareLists(Lottery& list2);

private:
int count;
int winner;
node * list;
};

//similar
Lottery :: Lottery ():list(NULL), count(0), winner(0)
{
}

{
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;
}
0

Associate 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

Author 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?

Thanks
Ben
0

Associate Director - Product EngineeringCommented:
Hi Ben!

This will help you pu numbers in a sorted order right when they are inserted:

bool AddNumber ( int number )
{
int i ;

if ( count == 5 )
return false ; // end if

for ( i = 0 ; i < count && arr[i] <= number ; i ++ )
; // end for

// loop stops when i == count or arr[i] > number. This is where number has to be inserted.

if ( i == count )
{
arr[count++] = number ;
return true ;

} // end if

for ( j = count ; j > i ; j -- ) // shift all elements one position ahead
arr[j] = arr[j-1] ; // end for

arr[i] = number ;
count ++ ;
return true ;

} // end of AddNumber ()

Hope that helps! It'll always put a number in its sorted place whenever it is called (even after clearing the array).

Mayank.
0

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

• 5
• 3
Tackle projects and never again get stuck behind a technical roadblock.