Help On A Quick Sort Program

Hello, i am writing a program for my data structures corse that sorts some numbers read in from a text file using quick sort. As you might tell i am new to programming (so go easy on the jargon)

I have tried to write and implement parts of source code given to us in examples but obviously incorrectly. The program uses an array with 2 values - the value of the number (other) and the origional position in the text file (key). The two main problems i think i am having is that it says overloaded member function for the sort and the adding in numbers function. (not sure how to get numbers into sort function). The compiler also doesnt like when i try and get or change things in the array
e.g. k = ptable[3].key; wont work. In the examples given to us this is a fine statement so i dont understand why its not ok..

Any help on any of the problems in my code will be greatly appreciated as i am a bit stuck. Thanks alot nick :)

Code:

---



#include <iostream.h>  // I/O
#include <fstream.h>  // file I/O
#include <stdio.h>
#include <conio.h>
#define MAX 1000000    //Defines the max amount of numbers that can be sorted by the algorithm, I have chosen 1000000 because it
                                                //is a sensible amount for the memory to handle


struct ipair {
        int key;
        float other;
        };

class table_of_pairs {
        int table_size;
        ipair *ptable;
        int num_in_table;

       
public:
        table_of_pairs(const int size)        {                               
                num_in_table = 0;
                ptable = new ipair[(table_size = size)+1];                // Set up an array of the requested size
                                                                                                               
                };

        ~table_of_pairs()                {delete [] ptable;};
        int add_to_table(ifstream);
        int quick_sort();
        };


void table_of_pairs::add_to_table()
        {
        int i;
        char others[40];

        ifstream fp_in("numbers.txt", ios::in);  // declare and open file numbers.txt

        while(others != 0)
                {
                for(i=0; i<MAX; i++)
                        {
                        cin >> others;
                        ptable[i].key = i;
                        ptable[i].other = others;
                        }
                }
                fp_in.close();  // close the streams
        }









int table_of_pairs::quick_sort(float darr[MAX], int lb, int ub)
        {
       
        float a;
        int up, down;
        float temp;          /* temporary variable, used in swapping */

        if (lb >= ub)
                return;

        a = darr[lb].other;
        up = ub;
        down = lb;

        while (down < up)
        {
        while (darr[down].other <= a)        /* scan the keys from left to right */
                    down++;
                while (darr[up].other > a)            /* scan the keys from right to left */
                up--;
            if (down < up)
                {
                    temp = darr[down].other;          /* interchange records */
                        darr[down].other = darr[up].other;
                        darr[up].other = temp;
                }
        }

        darr[lb].other = darr[up].other;                /* interchange records */
        darr[up].other = a;

        quick_sort(darr, lb, up-1);        /* recursive call - sort first subtable */
        quick_sort(darr, up+1, ub);        /* recursive call - sort second subtable */
        }

void main()
        {
        int key, mid, mi, md, firstkey, lastkey, size;
        float n, median, first, last;
        table_of_pairs mytable(MAX);
       
        mytable.add_to_table(size);
        size = sizeof(ptable)/sizeof(ptable[0]);
        //size = table_size;
        int lb = 0, ub;                                                /* upper and lower bound variables */
        ub = size;
        mytable.quick_sort(ptable, ub,lb);
       
        if(size%2==0)

        {
                n = size/2;
                mid = n;
                mi = n+1;
                md = (ptable[mid].other + ptable[mi].other)/2;
                key = ptable[md].key;
                median = ptable[md].other;
                cout << "The median value is" << median << "at line" << key;
                cout << "\n";

        }

        else
        n = (size/2) + 0.5;
        median = ptable[n].other;
        key = ptable[n].key;

        cout << "The median value is" << median << "at line" << key;
        cout << "\n";

        first = ptable[0].other;
        firstkey = ptable[0].key;

        last = ptable[size - 1].other;       
        lastkey = ptable[size - 1].key;
        cout << "The first value is" << first << "at line" << firstkey;
        cout << "\n";
        cout << "The last value is" << last << "at line" << lastkey;
        cout << "\n";


        }

---

Haven't looked in depth, but just a couple issues:

Code:

---

void main()

---

main should always return an int.

Quote:

---

Originally Posted by nick4

The compiler also doesnt like when i try and get or change things in the array e.g. k = ptable[3].key; wont work.

---

Probably because ptable is a private member variable and you are trying to access it directly from main (and attempting to access it incorrectly even if it weren't I might add). If it weren't private you could probably say something like:

Code:

---

k = mytable.ptable[3].key;

---

But you probably don't really want to do that. Maybe add a member function that returns the key value at a given index.

Code:

---

class table_of_pairs {
...
public:
    int add_to_table(ifstream);
    int quick_sort(/*Something goes here?*/);
};

void table_of_pairs::add_to_table(/*Something goes here?*/)
{
    ...
}

int table_of_pairs::quick_sort(float darr[MAX], int lb, int ub)
{
    ...
}

---

Your return types and arguments don't match up in the code fragments above.

Code:

---

#include <iostream.h>  // I/O
#include <fstream.h>  // file I/O
#include <stdio.h>
#include <conio.h>

---

Those headers should be:

Code:

---

#include <iostream>
#include <fstream>
#include <cstdio>  // Don't really seem to need this one at all
#include <conio.h>  // Don't really seem to need this one at all
using namespace std;

---

Quote:

---

Originally Posted by nick4

Hello, i am writing a program for my data structures corse that sorts some numbers read in from a text file using quick sort. As you might tell i am new to programming (so go easy on the jargon)

---

I'm surprised you'd be taking a data structures class if you're new to programming.

cheers for the help bud

i have alterd the class but how do i get table of pairs to be public so i can access it from main and still be in table of pairs

Code:

---


class table_of_pairs {
        int table_size;
        ipair *ptable;
        int num_in_table;
        int add_to_table(ifstream);       
        int quick_sort(int);       
       
public:
        table_of_pairs(const int size)        {                               
                num_in_table = 0;
                ptable = new ipair[(table_size = size)+1];                // Set up an array of the requested size
                                                                                               
                };

        }

---

Quote:

---

Originally Posted by nick4

how do i get table of pairs to be public so i can access it from main and still be in table of pairs

---

You have a public section already so all you would need to do is to put your ptable declaration underneath that public heading.

Code:

---

class table_of_pairs {
    int table_size;
    int num_in_table;
    int add_to_table(ifstream);       
    int quick_sort(int);       
public:  // See this here
    ipair *ptable;  // Put your ptable declaration under public
    table_of_pairs(const int size) {                               
        num_in_table = 0;
        ptable = new ipair[(table_size = size)+1];    // Set up an array of the requested size
                                                                                       
    }; // Should not be a semicolon here

};  // Should be a semicolon here

---

However, I suggested a function that would return the key value at a given index in the ptable variable. This would allow you to keep ptable private but still have access to it. It could look like this:

Code:

---

class table_of_pairs
{
  ...
public:
    ...
    int GetKey(int index) const
    {
        if( index < table_size ) return ptable[index].key;
        else ...  // Do something here to return a value you can recognise as being a error
    }
};

---

Or perhaps you could have the function return a bool and you could also pass in a second integer parameter (as a reference) that gets set if the index happens to be valid:

Code:

---

class table_of_pairs
{
  ...
public:
    ...
    bool GetKey(int index,int& key) const
    {
        if( index < table_size )
        {
            key = ptable[index].key;
            return true;
        }
        else return false;
    }
};

---

[edit]Once you've finished taking this class look up the map container. It could eliminate the need for most of the code you had to write.[/edit]

if i put in one of the above how would it be possible to write in the key value from another function?

say in add to table..

My main problem is when i try to write or read from the ptable eg.

others = ptable[i].other;
gives error
subscript requires array or pointer type
left of '.other' must have class/struct/union type

in other similar c++ programs given to us as examples this doesnt happen
would this be better?

Code:

---

public:       
                int GetKey(int index,int& key) const
            {
        if( index < table_size )
                {
                        key = ptable[index].key;
                }

        else return (-1);
                }
                                int Getother(int index,float& other) const
            {
        if( index < table_size )
                {
                        other = ptable[index].other;
                }

        else return (-1);
                }

                table_of_pairs(const int size)
                {                               
                num_in_table = 0;
                ipair *ptable;
                ptable = new ipair[(table_size = size)+1];                // Set up an array of the requested size
                                                                                               
                }

        };
...
...
int table_of_pairs::add_to_table(ifstream)
        {
        int i;
        float others;

        ifstream fp_in("numbers.txt", ios::in);  // declare and open file numbers.txt

        while(others != 0)
                {
                for(i=0; i<MAX; i++)
                        {
                        cin >> others;
                        mytable.Getkey(i , i);
                        mytable.Getother(i , others);
                       
                        }
                }
                fp_in.close();  // close the streams
        }

---

Quote:

---

Originally Posted by nick4

My main problem is when i try to write or read from the ptable eg.

others = ptable[j].other;
gives error
subscript requires array or pointer type
left of '.other' must have class/struct/union type

---

That's because ptable is a member of a class. Outside of a class, such as in your main function, you access members of a class by typing the particular class instance's name followed by the dot (.) operator (this is provided the data member is declared as public and therefore directly accessible). I.e.:

Code:

---

int main()
{
    table_of_pairs mytable(MAX);

    float others = mytable.pairs[0].other;
}

---

Within a class, you of course don't need to do that.

Code:

---

int GetKey(int index,int& key) const
{
    if( index < table_size )
    {
        key = ptable[index].key;
    }

    else return (-1);
}

int Getother(int index,float& other) const
{
    if( index < table_size )
    {
        other = ptable[index].other;
    }
    else return (-1);
}

---

Those should not compile correctly, you should be getting some sort of "Not all control paths return a value" type of error. The "if" blocks need to return a value indicating success. This is why I suggested a function that returns a bool true/false value, it just seems to make more sense to me personally.

Judging from what it seems you are trying to do, I don't think you would have a need to write to these key/other values beyond what you have during the initial loading of values from the file. If you did however, you could just add another couple member functions to the class:

Code:

---

class table_of_pairs
{
    ...
public:
    ...
    void SetKey(const int index,const int key)
    {
        if( index < table_size )
            ptable[index].key = key;
    }
    void SetOther(const int index,const int other)
    {
        if( index < table_size )
            ptable[index].other = other;
    }
};

---

Code:

---

int table_of_pairs::add_to_table(ifstream)
{
    int i;
    float others;

    ifstream fp_in("numbers.txt", ios::in);  // declare and open file numbers.txt
   
    while(others != 0)
    {

        for(i=0; i<MAX; i++)
        {
            cin >> others;
            mytable.Getkey(i , i);
            mytable.Getother(i , others);
        }
    }
    fp_in.close();  // close the streams
}

---

The GetKey and Getother functions are meant to be used from outside the class, i.e. from the main function. This allows your main function to indirectly access/read the values stored in the classes private area. Within the add_to_table function itself, the code has no knowledge of a mytable variable, this represents an instance of a class in the main function and nothing viable within the add_to_table function. Since a classes member functions already have access to anything in the class (regardless of it being private/public) you don't have any need to call these functions here. Just directly access the ptable variable as in your original post. [edit]Also saw your read code doesn't read from the file in the above code, modified it in the code below.[/edit]

Code:

---

int table_of_pairs::add_to_table(ifstream)
{
    int i;
    float others;

    ifstream fp_in("numbers.txt", ios::in);  // declare and open file numbers.txt

    for(i=0; i<MAX; i++)
    {
        fp_in >> others;
        ptable[i].key = i;
        ptable[i].other = others;
    }
    fp_in.close();  // close the streams
}

---

cheers mate that makes sense. when i am trying to call my quick sort from my main program do i put:
mytable.quick_sort(ptable, ub,lb);
i want to sort the table in order of the "other" values

Since your quick_sort function is a recursive one that calls itself and needs parameters that your main function has no need to know of, I would suggest making a public sort function that calls a private quick_sort function. The public sort function should not need any parameters passed into it. The public sort function would then call the private quick_sort function with the approriate values and hides the user of the class from needing to provide any data when he/she desires to sort the data in the main function. I'd implement this like so:

Code:

---

class table_of_pairs
{
    ...
    void quick_sort(float* darr, int lb, int ub);
public:
    ...
    void sort();
};

void table_of_pairs::quick_sort(float* darr, int lb, int ub)
{
    ...
}

void table_of_pairs::sort()
{
    // The public sort function calls the private quick_sort
    // this hides user in main from needing to have anything
    // to do with the internal workings of the class
    quick_sort(ptable,0,table_size);
}

int main()
{
    table_of_pairs mytable(MAX);
    ...
    mytable.sort();  // Call the public sort function, no parameters needed
}

---

cheers for that mate but it still gives me this error:

'quick_sort' : cannot convert parameter 1 from 'struct ipair *' to 'float *'

Sorry, I quickly used what you had in a previous post as a template for my posting. The error message is fairly self-explanatory. You need to change the type of the first parameter to the quick_sort function (do this in two places remember) from float to struct ipair*. And if your code for that function has not changes significantly from the first post, you might want to consider also swapping the key values when you swap the other values unless the pairings are no longer meant to match up to the way they were originally.