Thread: Help On A Quick Sort Program

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    7

    Question 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";
    
    
    	}

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    cheers for the help bud

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    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
    												
    		};
    
    	}

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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]
    Last edited by hk_mp5kpdw; 12-06-2004 at 07:49 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    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..

  7. #7
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    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
    	}

  8. #8
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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
    }
    Last edited by hk_mp5kpdw; 12-06-2004 at 09:19 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  9. #9
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    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

  10. #10
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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
    }
    Last edited by hk_mp5kpdw; 12-06-2004 at 10:12 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  11. #11
    Registered User
    Join Date
    Dec 2004
    Posts
    7
    cheers for that mate but it still gives me this error:

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

  12. #12
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Quick sort
    By Saiyanman in forum C Programming
    Replies: 4
    Last Post: 07-30-2002, 10:16 PM
  5. quick termination of program
    By jobolikescake in forum C Programming
    Replies: 7
    Last Post: 01-20-2002, 10:59 PM