C++ Sorting Names Problem (Quicksort)

[hanleychan]

Hi,
I started C++ not long ago and I am having trouble with an assignment. I am susposed to read from a file a list names in the format.

num (number of names in this list)
"surname initial,first name"
"surname initial,first name"
"surname initial,first name"
.... until there are num records

I am then susposed to sort the list using quick sort first by surname and then by first name. After sorting the list I have to display the list of names in upper case letters and proceed to sort the next list of names in the file until end of file. I think I am finished everything except the sorting. I am totally stuck and have no idea how to do it

Here is what i have done so far

#include <iostream>
#include <assert.h>
#include <iomanip>
#include <cstdlib>
#include <string.h>
#include <stdio.h>
#include <fstream>

#define MAX_NAME_SIZE 50    // Maximum character length of a full name

using namespace std;

typedef char *charPtr;
typedef charPtr *nameType;

// Prototypes
nameType sortNames(nameType names);
nameType createNameStorage(unsigned numNames);
void displayUpper(nameType names, unsigned numNames);
void deleteNames(nameType names,unsigned numNames);
void quickSort(nameType names,int start,int endInd);



nameType createNameStorage(unsigned numNames)
{
    nameType names;
    names = new charPtr[numNames];
    assert(names != NULL);

    return names;
}


void displayUpper(nameType names,unsigned numNames)
{
    for (int jj = 0;jj < numNames;jj++)
    {
        for(int ii = 0;names[jj][ii] != '\0';ii++)
        {
            if(names[jj][ii] >= 'a' && names[jj][ii] <= 'z')    
                cout << (char)('A' + names[jj][ii] - 'a');
            else
                cout << names[jj][ii];
        }
        cout << endl;
    }
}



void deleteNames(nameType names,unsigned numNames)
{
    for (int jj = 0;jj < numNames; jj++)
        delete[] names[jj];
    delete names;
}

// Does not work
/*
void quickSort(nameType names, int start, int end)
{
    int i = start, // set i to the start of the interval
         j = end;  // set j to the end of the interval
    char *mid = names[(start+end)/2]; // pick the middle value as the dividing point
    char temp[MAX_NAME_SIZE];
      
  
    while( i <= j )  // loop while i and j do not overlap
    {
       while( names[i] < mid ) // search for a value greater than or equal to the mid value
          i++;
       while(names[j] > mid) // search for a value less than or equal to the mid value
          j--;

       if ( i <= j ) // if i is less than j, swap the two values
        {
         //  temp = names[i];
            strcpy(temp,names[i]);
            names[i] = names[j];
            names[j] = temp;
              i++;   // increment i
              j--;  // decrement j
        }
        if( j > start )
            quickSort( names, start, j ); // recursively call quickSort for interval on the left
        if( i <end )
            quickSort( names, i, end); // recursively call quickSort for interval on the right
    }
}
*/


int main()
{
    const int noNames = 0;
    nameType names;
    
    unsigned numNames;                // Number of names in a group
    char nextList;                    // Decides whether to sort and display the next group of names
    char Buffer[MAX_NAME_SIZE];        // Holds full name


    cout << "This program gets a list of names from assign_3_data.txt and then it sorts" << endl
         << "and outputs the list of names in upper case letters." << endl;
         
    // Open file that contains list of names
    ifstream inFile("assign_3_data.txt");
    
        
    
    if(!inFile.eof())
    {
        do
        {    
            inFile >> numNames;
        
            // Check for no names in a list
            if (numNames == noNames)
                cout << "No names in this list" << endl;
            
            // Preform sorting/display only if numNames is not 0
            else
            {
                names = createNameStorage(numNames);
                inFile.getline(Buffer,MAX_NAME_SIZE);
                
    
                // Dynamically store the names
                for(int jj = 0; jj < numNames;jj++)
                {
                    inFile.getline(Buffer,MAX_NAME_SIZE);
                    names[jj] = new char[strlen(Buffer)+1];    
                    assert(names[jj] != NULL);
                    strcpy(names[jj],Buffer);
                }
            //    quickSort(names,0,numNames-1);
            
                displayUpper(names,numNames);
                deleteNames(names,numNames);
            }
            
        
            // Ask if user wants to sort next list of names if not at end of file
            if(!inFile.eof())
            {
                do
                {
                    cout << "\nDo you want to sort the next list of names? (y/n)";
                    cin >> nextList;
            
                    // Error checking
                    if (nextList != 'y' && nextList != 'Y' && nextList != 'n' && nextList != 'N')
                        cout << "Invalid choice";
                }while(nextList != 'y' && nextList != 'Y' && nextList != 'n' && nextList != 'N');
            }
            
        // exit if end of file
        if (inFile.eof())
            nextList = 'n';
            
        }while(nextList == 'y' || nextList == 'Y');
    }
    
    if(inFile.eof())
        cout << "\nEnd of file";

    // Close file
    inFile.close();
    
    return 0;
}

Here is the assign_3_data.txt file

30
Yuen V, Daniel
Bedard B, Jason
English C, Robert
Ghani D, Saem
Zhang W, Li 
Cheng A, Chi-Ho 
Ding B, Naichun 
He E, Qiushi
Behnoosh J, Ali  
Hui F, Calvin
Imanuel G, Toar
Koufakis H, Tom
Myles N, Jeffery
Rubenstein O, Joshua
Kwan I, Jason 
Lee J, Ivan 
Yuen V, Danial
Liu M, Mi
Tian S, Zue
Abtin A, Farbod
Lin K, Ling-Yu 
Shum P, Wai 
Smirnov Q, Rostyslav 
Tian S, Xue
Tian S, Guo
Supangkat R, William
To T, Man
Castro K, Monica
Chen L, Jin
Wang U, Songzhao
1
Wang U, Songzhao
0
2
Tian S, Xue
Tian S, Guo
3
Tian S, Xue
Smirnov Q, Rostyslav
Tian S, Guo

 

[MRD]

Do you understand the algorithm for quicksort?

Also, when you implement it, it will be implemented recursively. Make sure you randomize the pivot or you get stuck with n^2 as a worst case scenario if the list is already mostly sorted. You can implement it as a function pointer, and then provide a comparison function, or you can just make a version of quicksort that works on your data type.

BTW, I think quicksort is already implemented in ansi C++, if you are allowed to use that. Even if not, you may want to take a look at it to see how they do it.

 

[hanleychan]

not really understand fully. I managed to get the list of names to sort as long as the list is from 0-2 names. Now I'm stuck and don't know how to get the rest of the quick sort to work.

/**
 * Name: Hanley Chan
 * StudentID: 100068434	AccountID: hchan003
 * Course: CPSC 1160    Section#: 1
 */
 
/**
 * Description: This program asks the user if they want to sort a list of names and then it will
 * proceed to sort the list and output the sorted list of names in upper case letters.  It first 
 * sorts the list by surname and then by first name.
 */

#include <iostream>
#include <assert.h>
#include <iomanip>
#include <cstdlib>
#include <string.h>
#include <stdio.h>
#include <fstream>

#define MAX_NAME_SIZE 50	// Maximum character length of a full name

using namespace std;

typedef char *charPtr;
typedef charPtr *nameType;


// Prototypes
nameType sortNames(nameType names);
nameType createNameStorage(unsigned numNames);
void displayUpper(nameType names, unsigned numNames);
void deleteNames(nameType names,unsigned numNames);
void quickSort(nameType names,int loBound,int hiBound);


/**
 *	Sorts a list of names
 *	
 *	@param names the list of names to sort
 *	@param loBound left end
 *	@param hiBound right end
 */
void quickSort(nameType names,int loBound,int hiBound)
{
	char pivot[MAX_NAME_SIZE];
	int loSwap;
	int hiSwap;
	char temp[MAX_NAME_SIZE];
	
	// Sort 1 name
	if (loBound >= hiBound)
		return ;
	
	// Sort 2 names
	if (hiBound - loBound == 1)
	{
		int length1 = strlen(names[loBound]);
		int length2 = strlen(names[hiBound]);
		int lengthMax;
		
		if (length1 > length2)
			lengthMax = length1;
		else 
			lengthMax = length2;

		for(int jj = 0;jj < lengthMax;jj++)
		{		
			while (names[loBound][jj] == names[hiBound][jj])
				jj++;
				
			if (names[loBound][jj] > names[hiBound][jj])
			{
				strcpy(temp,names[hiBound]);
				strcpy(names[hiBound],names[loBound]);
				strcpy(names[loBound],temp);
				return;
			}
		}
	}
	
	
	/**Doesn't work properly
	// Sort 3 or more names
	strcpy(pivot,names[(loBound+hiBound)/2]);
	strcpy(names[(loBound)],pivot);
	loSwap = loBound + 1;
	hiSwap = hiBound;
	
	do
	{
		while(loSwap <= hiSwap && names[loSwap] <= pivot)
			loSwap++;
		while(names[hiSwap] > pivot)
			hiSwap--;
		if(loSwap < hiSwap)
		{
			strcpy(temp,names[loSwap]);
			
			strcpy(names[loSwap],names[hiSwap]);
			strcpy(names[hiSwap],temp);
		}
	}while (loSwap < hiSwap);
	strcpy(names[loBound],names[hiSwap]);
	strcpy(names[hiSwap],pivot);
	quickSort(names,loBound,hiSwap-1);
	quickSort(names,hiSwap+1,hiBound);*/
}


/**
 * Allocates memory to store a list of names
 *
 * @param numNames the number of names
 * @return names memory to be used to store names
 */
nameType createNameStorage(unsigned numNames)
{
	nameType names;
	names = new charPtr[numNames];
	assert(names != NULL);

	return names;
}


/**
 * Displays a list of names in upper case
 * 
 * @param names the list of names
 * @param numNames the number of names in the list
 */
void displayUpper(nameType names,unsigned numNames)
{
	for (int jj = 0;jj < numNames;jj++)
	{
		for(int ii = 0;names[jj][ii] != '\0';ii++)
		{
			if(names[jj][ii] >= 'a' && names[jj][ii] <= 'z')	
				cout << (char)('A' + names[jj][ii] - 'a');
			else
				cout << names[jj][ii];
		}
		cout << endl;
	}
}



/**
 * Deletes a list of names from memory
 *
 * @param names the list of names to delete
 * @param numNames the number of names in the list
 */
void deleteNames(nameType names,unsigned numNames)
{
	for (int jj = 0;jj < numNames; jj++)
		delete[] names[jj];
	delete names;
}


/**
 * Main function
 */
int main()
{
	// Constants
	const int noNames = 0;

	// Variables
	nameType names;
	unsigned numNames;				// Number of names in a group
	char nextList;					// Decides whether to sort and display the next group of names
	char Buffer[MAX_NAME_SIZE];		// Holds full name



		
	// Description of program
	cout << "This program gets a list of names from assign_3_data.txt and then it sorts" << endl
	     << "and outputs the list of names in upper case letters." << endl << endl;
	     
	// Open file that contains list of names
	ifstream inFile("assign_3_data.txt");
	
	// Checks if "assign_3_data.txt" exists in working directory
	if(!inFile)
		cout << "Error trying to open \"assign_3_data.txt\"" << endl;
	else
	{
		// Check for end of file
		if(!inFile.eof())
		{
			do
			{	
				inFile >> numNames;
		
				// Check for no names in a list
				if (numNames == noNames)
					cout << "No names in this list" << endl;
			
				// Preform sorting/display only if numNames is not 0
				else
				{
					names = createNameStorage(numNames);
					inFile.getline(Buffer,MAX_NAME_SIZE);
				
	
					// Dynamically store the names
					for(int jj = 0; jj < numNames;jj++)
					{
						inFile.getline(Buffer,MAX_NAME_SIZE);
						names[jj] = new char[strlen(Buffer)+1];	
						assert(names[jj] != NULL);
						strcpy(names[jj],Buffer);
					}

					
	
			quickSort(names,0,numNames-1);
					
			displayUpper(names,numNames);
					deleteNames(names,numNames);
				}
					
				// Ask if user wants to sort next list of names if not at end of file
				if(!inFile.eof())
				{
					do
					{
						cout << "\nDo you want to sort and display the next list of names? (y/n)";
						cin >> nextList;
			
						// Error checking
						if (nextList != 'y' && nextList != 'Y' && nextList != 'n' && nextList != 'N')
							cout << "Invalid choice";
					}while(nextList != 'y' && nextList != 'Y' && nextList != 'n' && nextList != 'N');
				}
			
				// exit if end of file
				if (inFile.eof())
					nextList = 'n';
				}while(nextList == 'y' || nextList == 'Y');
			}
	
	}
	// End of file message
	if(inFile.eof())
		cout << "\nYou have reached the end of the file." << endl;

	// Close file
	inFile.close();
	
	return 0;
}

 

[MRD]

Take a loot at: http://en.wikipedia.org/wiki/Quicksort

It includes an explanation of how the algorithm works and even some implementations in various languages. Don't just copy it though, try to understand it. =p

 

[hanleychan]

thanks