Thread: Sort by population or area

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    22

    Sort by population or area

    Hey guys, I'm supposed to write a program that takes census information from a file provided by the user and sort it by population or area.

    I think I did most of the functions correctly, but I'm having trouble starting the function that actually sorts the data.

    I was given the prototype for the function, but I have no idea where to start. This is my first time working with C-strings and it's causing me a lot of trouble!

    Here was the prototype I was given:

    Code:
    Sort the arrays by population or area. Notice that you have to sort all three arrays together, using either integer array to control the process. (Important: You only need one function for sorting by either population or area. A simple trick with argument passing will control which one controls the sorting.) This means that you have to modify the sorting function that you've used in the past so that it has parameters for three arrays and treats one array as a special "key array" during the sorting process. The function prototype could look like this: 
    
    void sortPopulationUnits(char names[][MAX_NAME_LENGTH+1],
                             int keyArray[],
                             int otherIntArray[],
    			 unsigned int nUnits);
    I really don't understand what they mean by treating one array as a "key array", and whats with the "unsigned int nUnits" in the prototype?

    If anyone could give me any hints at how to go about implenting this function, I would greatly appreciate it!



    Code:
    // This program helps people look at population information by sorting 
    // data in given files.
    
    
    #include<iostream>
    #include<fstream>
    #include<cstring>
    using namespace std;
    
    
    const int MAX_NAME_LENGTH = 24;
    
    //Function Prototypes.
    
    int readIntArray(int arr[], int maxSize, char fname[]);
    int readStringArray(char arr[][MAX_NAME_LENGTH+1], int maxSize, char 
    fname[]);
    void sortPopulationUnits(char names[][MAX_NAME_LENGTH+1], int keyArray[], 
    int otherIntArray[], unsigned int nUnits);
    int mainMenu();
    
    
    // Main function.
    
    int main()
    {
      int current_array_size = 0;
      const int maxSize = 200;
      int population[maxSize];
      int area[maxSize];
      const int MAX_NAME_LENGTH = 24;
      char fname[MAX_NAME_LENGTH + 1];
      char names[maxSize][MAX_NAME_LENGTH + 1];
    
      cout << "Enter name of population unit name file: ";
        cin >> fname;
    
      current_array_size = readStringArray(names, maxSize, fname);
    
      cout << "Enter name of population file: ";
        cin >> fname;
    
      readIntArray(population, maxSize, fname);
    
      cout << "Enter name of area file: ";
        cin >> fname;
    
      readIntArray(area, maxSize, fname);
      
      //read in contents of population.
    
    
    //Main Menu.
      
      int selection = mainMenu();
      while ((selection > 0) && (selection < 5))
    	{
    	if (selection == 1){
    	  cout << "1";
    	  selection = mainMenu();
    	  //sort function...
    	}
    	else if (selection == 2){
    	  cout << "2";
    	  selection = mainMenu();
    	  //sort function...
    	}
    	else if (selection == 3){
    	  cout << "3";
    	  selection = mainMenu();
    	  //write file function...
    	}
    	else // if selection == 4
    	  return 0;
           	  //exit program.
    	}
    }
    
    
    
    //Function definition.
    
    int mainMenu()
    { 
      int selection = 0;
      do{
            cout << "Main menu: " << endl;
            cout << "(1) Sort by population" << endl;
            cout << "(2) Sort by area" << endl;
            cout << "(3) Write to output file" << endl;
            cout << "(4) Quit" << endl;
            cout << "Your choice: ";
            cin >> selection;
        }
    
            while((selection < 1) || (selection > 4));
    	
    	return selection;
    }
    
    
    
    int readIntArray(int arr[], int maxSize, char fname[])
    {
      int i=0;
      fstream fin.open(fname);
      if(fin.fail()){
    	cout << Error this file does not exist." << endl;
    	end(1);
      }
    
      for(i; i < maxSize; i++){
    	fin >> arr[i];
      }
      	fin.close();
    	return i;
    
    
    }
    
    int readStringArray(char arr[][MAX_NAME_LENGTH+1], int maxSize, char fname[])
    {
      int c=0;
      int r=0;
      fstream fin.open(fname);
      if(fin.fail()){
    	cout << Error this file does not exist." << endl;
    	end(1);
    }
     
      for(c=0; c < maxSize; c++)
      {
    	for(r=0; r < MAX_NAME_LENGTH+1; r++)
               fin >> arr[c][r];
    
    	arr[c][r+1] = '\0';
    
    	return c+1;
      }
    
      
    
    }
    void sortPopulationUnits(char names[][MAX_NAME_LENGTH+1], int keyArray[], int otherIntArray[], unsigned int nUnits)
    {
    
    }
    Thanks in advance!

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    You have 3 files. They are all simple lists.

    One file is the Areas files.
    The other files is a Population file.
    And yet another is the Population Units file.

    All files are ordered. So, the first Area on the first file corresponds to the first population number on the second file, and the first population unit on the third file.

    You load each of these files into a separate array.

    Now, you are being asked to sort these arrays by either population or area. The problem with sorting one array and leaving the other ones untouched would then be that position 1 in the first array would not correspond anymore to position one on the second array and third array. As you sort, you need to also reposition the other arrays so that all arrays match.

    And that is basically what you are being asked.
    The keyArray is thus... the array you are being asked to sort. The key of the sort.
    The otherIntArray is the other array (population if you are sorting by area, or area if you are sorting by population).
    The names is the population units array which can never be the key for the sort.

    As for nUnits... remember what you have learned in class about arrays? They have no bounds checking. You have to tell the sort function when to stop. The function needs to know the size of the arrays otherwise the more than necessary loop you will have to create inside the sort function would go out of bounds. nUnits is thus the size of the arrays.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    22
    Hmmm...thanks so much for your explanation! I understand what you're saying, but I'm having a lot of trouble implementing the ideas into the code...is this even considered a start for the sort?

    Code:
    void sortPopulationUnits(char names[][MAX_NAME_LENGTH+1], int keyArray[], int otherIntArray[], unsigned int nUnits)
    {
    	for(int i=0; i < nUnits; i++){
    		if ((keyArray[i]) > keyArray[i+1])){
    			
    			int temp = keyArray[i];
    			int temp1 = otherIntArray[i];
    			
    			keyArray[i] = keyArray[i+1];
    			keyArray[i+1] = temp;
    
    			otherIntArray[i] = otherIntArray[i+1];
                            otherIntArray[i+1] = temp1;
    
    			
                
    
    
    }
    Any help would be appreciated!

    Thanks in advance!

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    I don't know what sort algorithms you have learned in class. My take is it was probably a bubble sort. The following is a bubble sort pseudo code. Try to work from there...

    Code:
        endless_loop
            boolean has_swapped = 0  // flag to control exit from loop and sort of other arrays
            for number i from 1 to (arraysize - 1)
                if keyarray[i] > keyarray[i + 1]  // they are in the wrong order
                    swap keyarray[i] with keyarray[i + 1] 
                    has_swapped = 1  // there was at least one swap.
                if has_swaped = 1  // if there was a swap, mirror it on the other arrays
                    swap namesarray[i] with namesarray[i+1]
                    swap otherarray[i] with otherarray[i+1]
                endif
            endfor
            if has_swapped = 0  // no swaps were made on the last pass. keyarray is sorted 
                break
            endif
        endloop
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  3. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  4. Need help with switch
    By 3kgt in forum C Programming
    Replies: 2
    Last Post: 02-26-2003, 12:43 PM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM