Solved

# Class, Array Sort on Insert - EASY - help :)

Posted on 2003-03-18
Medium Priority
288 Views
--------------------
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
Question by:killer455
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 5
• 3

LVL 30

Expert Comment

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

LVL 1

Expert Comment

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

LVL 30

Expert Comment

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

LVL 30

Expert Comment

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

LVL 1

Expert Comment

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

LVL 30

Expert Comment

ID: 8164707
>> 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 Comment

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

LVL 30

Accepted Solution

Mayank S earned 100 total points
ID: 8171602
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

LVL 1

Expert Comment

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there isâ€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
###### Suggested Courses
Course of the Month9 days, 4 hours left to enroll