We help IT Professionals succeed at work.

Isertion Sort - When To Do It?

BenFate12043
BenFate12043 asked
on
261 Views
Last Modified: 2010-08-05
My program reads from a file and splits up each line into three variables. My problem is, I need the lines in order based on the first variables. I don't know how to do it though. The file is opened in one classed, and read from another. The first class has an array of the second class. I have no array to sort in the second class, so would I have to sort in the first class? I was thinking I could sort in the second class based on the first variable, but instead of just moving each one up a position, I would have to move each one in each array up. That seemed liked a little too much work, then I realized the no array thing. My second guess is to open the file, read the whole thing, sort it, then pass it into the other function to split up the variables. I don't really know if that possible. Anyone  have any suggestions?
Comment
Watch Question

Commented:
Suppose your file is in this format

12 10 This is first line
4   11 This is line 2
...

...
..


Now, if you know the format of file for example, I know that the first variable is 4 bytes(int), followed by second (4bytes int) and followed by 10 bytes (char *)

Now, declare a struct/class with this structure
Eg
typedef struct rec {
    int first ;
    int second ;
    char third[10] ;
};


Now, declare the class with this structure as data and now sort on the first column of the structure and move (insertion sort) the whole structure variable rather than each element (since assigning of structure variable as such is possible )


U can also have this struct as a internal class into your main class

Amit

Author

Commented:
I've been working on this for quite a while, and I really don't want to do anything major, like change the class.

class CA{
private:
      char aNumber[ACCT_NUMBER_LENGTH+1];
      char chold[NAME_LENGTH+1];
      double balance;
public:
      bool readA(std::ifstream &);
};

class AL{
private:
      CA myarray[MAX];
      void inserSort(void);
      std::ifstream accFile, transFile;
      std::ofstream logFile;

public:
      AccountList(void);
      ~AccountList(void);
      bool openAFile(void);
      bool openTFile(void);
      int processTransactions(void);
      void setFileName(char x[MAX_FILENAME_LEN]);
      void setTFileName(char x[MAX_FILENAME_LEN]);
};

I use the setFileName function to pass in the file and set it to accFile. I use the openAFile to open the file and call the CA readfile from a loop. That gets the current line and splits up a number which is stored as a char [17], a string stored as a char[25], and a number stored as a double. The loop in openAFile gets all the lines.

My problem is, I now have the data in a different class. Should I sort it anyway, or should I try to sort it before it gets read, like an array that reads each line into an array, sorts that array, then the read file gets the lines from the array, and splits them up?

Commented:
See, whatever porblem you are facing
There can be only one solutions to it

1. Just declare CA as struct rather than class as declared in your above declaration (as by default, the struct menbers are public )

That is because,
In CA, you cannot sort because u have only row in it while in AL, u have all the rows, but u cannot sort in AL, as the data members of CA class are private.

2. Or u can declare the datamebers on CA as public

Amit

Author

Commented:
What if I make get and set public methods in CA. Then could I sort in AL?

Commented:
Yes, in fact you do not need to provide set method

Just proivde a get() method for the column on which you want to sort because that is the only value you required to access.

Thus, in the process of insertion sort, compare this column of the two CA objects [using get() for this to_be_sorted_on column], if you feel the object should move, just move the whole object into a the new position
This moving of whole object is possible since u are having access to all the objects in your AL class.

Amit

Author

Commented:
So I would have something like:

for(int j = 2 to numA) {
key = A[j];
int i = j - 1;
(while i > 0 and A[i] > key) {
  A[i+1] = A[i];
  i = i - 1;
}
 A[i+1] = key;
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Author

Commented:
It's not working. All that does is switch the first one with the second one. I am sorting by the aNumber, which is a char, does that matter?
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Commented:
I think that the reason the code Sys_Prog did not work is the way the temp variable got left out of the swapping process

CA temp ;

n=end; //your array size

for ( int i = 0  ; i < n ; i++ ) //since i < n , will break before j > n
{
 temp = myarray [i] ;
 j = i+1 ; // start inner loop at next item

    while (1) //inner loop
   {
          // if condition met
          if( myarray [j].getbalance()  >  myarray [i].getbalance())
           {
            //swap em
            temp=myarray[i];
            myarray[i]=myarray[j];
            myarray[j]=temp;
           }//endif

    j++;
    if(j==n)break;
    }//endwhile

}//end for


RJ

Commented:
Opps. Take out the temp= myarray[i]; unecessary

CA temp ;

int j=0;
int n=end; //your array size

for ( int i = 0  ; i < n ; i++ ) //since i < n , will break before j > n
{
 j = i+1 ; // start inner loop at next item

    while (1) //inner loop
   {
          // if condition met
          if( myarray [j].getbalance()  >  myarray [i].getbalance())
           {
            //swap em
            temp=myarray[i];
            myarray[i]=myarray[j];
            myarray[j]=temp;
           }//endif

    j++;
    if(j==n)break;
    }//endwhile

}//end for

Later you may like checking out things like
list <CA> MyCAList;

Very powerful and clean.


RJ

Author

Commented:
If I set an element in the array = to \0, and then, then call sort, would it just delete that and sort the rest?

Commented:
>>If I set an element in the array = to \0, and then, then call sort, would it just delete that and sort the rest?

No.

It would sort by comparison whatever the value of \0 (null) was compared to the other elements.

That is one of the problems with having elements in an array. You would have to modify the size of an array by copying the whole thing to some other place in memory and then delete the array and re-create it.

OR simply ignore null values and keep the array you have.

f( myarray[j]!= NULL &&
myarray [j].getbalance()  >  myarray [i].getbalance())

That is why people use things like list and link list. A list or link list can grow or shrink on demand (change size dynamically).

So you can remove an item.

A link list is simply a list created by items having pointers to the next item. To remove an item, the item before the one removed's pointer gets pointed to the item after the one being removed. Then the one removed is deleted and the list remains intact.

For an array your stuck in terms of array size. The most you can do is put values that you know are meaningless. Values way too large for normal operation like 99999999 or way too small or imposible like -1.

You can choose depending on your sort as to where you want the deleted items to appear. Maybe bottom of the sort, maybe top.

Knowing that you have items that represent empty items. You may need to impliment logic to ignore when your using the sorted results.

RJ

Author

Commented:
I'm sorting an array of 25, but it only has 6 items. Could't I just send it to the back with the other's that aren't being used?  

Commented:
Sure.

In above example you could set the value of the balance to -1 so that getbalance would return -1. Then if your comparing for the greatest value ( if this getbalanc() > next getbalance()  swap )

So say your six examples would be like this

123
122
120
15
14
12
-1
-1
-1
.... (25 entries)

The array elements that contained -1 would signify deleted or to be ignored values when you go to DISPLAY the results.

Or it could be a high value that may work better. Ignoring the 999999 entries

12
14
15
120
122
123
9999999
9999999
9999999
etc...

RJ
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.