Sorting two lists into one?

This is a discussion on Sorting two lists into one? within the C++ Programming forums, part of the General Programming Boards category; Hello I must merge two text files which contain a variable number of numbers. Both of these text files are ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    4

    Sorting two lists into one?

    Hello I must merge two text files which contain a variable number of numbers. Both of these text files are sorted from lowest to highest value and when they are merged into one list must retain this property.

    My friend and I were working on developing code for this but we have no idea if this is right. This is what we have so far...

    Code:
    #include <iostream>
    #include <string>
    #include <fstream>
    #include <sstream>
    #include <cstdlib>
    #include <vector>
    #include <list>
    
    int main(int argc, char argv[])
    {
    
    using namespace std;
    
    ifstream in_stream1;
    ofstream out_stream;
    ifstream in_stream2;
    
    in_stream1.open("prob2list1.txt");
    in_stream2.open("prob2list2.txt");
    out_stream.open("prob2merged.txt");
    
    int num1;
    int num2;
    int i;
    int j;
    
    int mergeList[10000];
    
    
    while(in_stream1.eof!=0)
    {
    in_stream1>>num1;
    mergeList[i]= num1;
    i++;
    }
    
    while(j<i)
    {
    in_stream2>>num2;
    if(mergeList[j]>num2)
    j++;
    else
    {
    if(j==0)
    {
    mergeList.insert(j,1);
    mergeList[0]=num2;
    }
    else
    {
    mergeList.insert(j,1);
    mergeList[j-1]=num2;
    }
    j++;
    }
    }
    
    return 0;
    }
    We're really quite confused and so we just tried to sort if using a really,really large array but when we try to compile it we receive these errors:

    Line 30 - Error:Invalid use of member<did you forget the &?>
    Line 46 - Error:Request for member 'insert' in 'mergeList', which is of non-class type 'int[10000]'
    Line 51 - Error:Request for member 'insert' in 'mergeList', which is of non-class type 'int[10000]'

    I know this code probably won't do the job in the first place and so any assistance would be greatly appreciated,thanks.

    I'm quite new at this so please excuse any errors.

  2. #2
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    Whoa, why do you need a Ten THOUSAND element array if you are using lists and vectors! Just read both files into the list and then sort the list.

    Or you can read the first value you of both files, which ever is the lowest/highest (depending on the sort order in the files) you put into your list first, then read a new value from that file and compare again untill you hit EOF in one file, then write the rest of it to your list.

    Or you can skip the list and write directly to the output file.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    4
    Thanks for your suggestions,I'll try working on them tomorrow morning and I'll tell you how they go.

    If we wanted to do the exact same thing as the above but this time sort a list of a KNOWN size(say 1000 numbers in each file),could we use a bubble sort function to do so?

    We have this code...

    Code:
    #include <iostream>
    #include <string>
    #include <fstream>
    #include <sstream>
    #include <cstdlib>
    #include <vector>
    #include <list>
    
    int main( )
    {
    
      using namespace std; 
      
      ifstream in_stream1;
      ofstream out_stream;
      ifstream in_stream2;
    
      in_stream1.open("prob2list1.txt");
      in_stream2.open("prob2list2.txt");
      out_stream.open("prob2merged.txt");
      
      int numbers[2000];
      int array_size;
      int num;
      int i,j;
    
        while(i<2000)
        {
          in_stream1>>num;
          numbers[i]=num;
          i++;
        }
      
    
      void bubbleSort(int numbers[], int array_size);
      {
      int i, j, temp;
    
      for (i = (array_size - 1); i >= 0; i--)
      {
        for (j = 1; j <= i; j++)
        {
          if (numbers[j-1] > numbers[j])
          {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
          }
        }
      }
      }
    
       bubbleSort(numbers, 2000);
    
        while(j<2000)
          {
    	numbers[j]=num;
    	out_stream<<num<<"\n";
    	  }
      
      return 0;
     }
    We only have one error and its this...

    "undefined reference to 'bubbleSort<int*, int>'
    collect2: ld returned 1 exit status"


    I have never seen this error before,whats up?

  4. #4
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    You can't define a function -- in this case bubbleSort() -- within another function -- also in this case, main().

    Incidentally, this is a programming assignment, correct?
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you have two sorted lists or vectors, you might be able to use std::merge or std::inplace_merge from the "algorithm" header to merge them.

    To sort something, "algorithm" contains a std::sort function and this works with regular arrays too. It's usually a lot faster than bubble sort (except if the array is already sorted, bubble sort would take O(n) time - if the algorithm also checks if the array is sorted.

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    4
    Quote Originally Posted by zx-1
    You can't define a function -- in this case bubbleSort() -- within another function -- also in this case, main().

    Incidentally, this is a programming assignment, correct?

    How would I go about solving this problem?

  7. #7
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    1. Grab your mouse and highlight everything from void bubbleSort(int numbers[], int array_size); down to its closing brace.
    2. Press CTRL-X.
    3. Move the cursor after the last closing brace of main().
    4. Press CTRL-V.
    5. Delete the trailing semicolon marked in red above.
    6. Move the cursor in between #include <list> and int main().
    7. Type void bubbleSort(int numbers[], int array_size);.
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

  8. #8
    Registered User
    Join Date
    Oct 2006
    Posts
    4
    Alright so I did as you suggested and it compiled just fine but when I ran it it created the output file but the file size was increasing at an astronomical rate(when it crashed it was at 300mb). Is this an infinite loop of some sort?

    Code:
    #include <iostream>
    #include <string>
    #include <fstream>
    #include <sstream>
    #include <cstdlib>
    #include <vector>
    #include <list>
    void bubbleSort(int numbers[], int array_size);
    
    int main( )
    {
    
      using namespace std; 
      
      ifstream in_stream1;
      ofstream out_stream;
      ifstream in_stream2;
    
      in_stream1.open("prob2list1.txt");
      in_stream2.open("prob2list2.txt");
      out_stream.open("prob2merged.txt");
      
      int numbers[2000];
      int array_size;
      int num;
      int i,j;
    
        while(i<2000)
        {
          in_stream1>>num;
          numbers[i]=num;
          i++;
        }
      
    
    bubbleSort(numbers, 2000);
    
        while(j<2000)
          {
    	numbers[j]=num;
    	out_stream<<num<<"\n";
    	  }
    
       
     
    
    
    
      
      return 0;
     }
    
    
    void bubbleSort(int numbers[], int array_size)
      {
      int i, j, temp;
    
      for (i = (array_size - 1); i >= 0; i--)
      {
        for (j = 1; j <= i; j++)
        {
          if (numbers[j-1] > numbers[j])
          {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
          }
        }
      }
    }

  9. #9
    Registered User
    Join Date
    Oct 2004
    Posts
    151
    See your second while loop.

    And you are using i and j uninitialized.

    And bubble sort is going to yield horrendous performance if the files have any size to them, but no need to worry about that just yet.
    Last edited by zx-1; 10-04-2006 at 01:29 AM.
    System: Debian Sid and FreeBSD 7.0. Both with GCC 4.3.

    Useful resources:
    comp.lang.c FAQ | C++ FQA Lite

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. Lists (sorting)
    By ultimo12345 in forum C Programming
    Replies: 2
    Last Post: 11-10-2008, 10:43 PM
  3. sorting in linked lists
    By vice in forum C Programming
    Replies: 2
    Last Post: 05-07-2005, 10:07 PM
  4. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  5. Sorting Linked Lists (code not concept)
    By Newbie Magic in forum C++ Programming
    Replies: 2
    Last Post: 05-11-2004, 08:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21