Archived

This topic is now archived and is closed to further replies.

PuterPaul

Inserting in order

Recommended Posts

Quick logic question really, I have a program which generates a random list of numbers, and is supposed to insert the numbers into the list in order. Here''s what I''ve written so far, i think my logic my be flawed though due to scope.


// insert input_item to an ordered list, the list must be still in

// correct order after the insertion. return the size of list. 

// TASK 1 -- add you code here

public int insertInOrder(String input_item)
{ 
   int i,j,insertPos;
   if(current_size>0)
   {
       int conversion = Integer.parseInt(input_item);	   
       for(i=current_size;i>conversion;i--)
           tmp[i+1]=data[i];  //temporary buffer

       for(j=0;j<=current_size+1;j++)
       {
           if(input_item.equals(data[j]) | Func.lessThan(input_item,data[j]))
	      data[j]=input_item;
       }
       current_size++;
   }
   else
   {   
   data[0] = input_item;     
   current_size++;
   }
   return current_size;
}
Oh and here''s how Func.lessThan is defined
public static boolean lessThan(String s1, String s2) 
// compare two strings s1 and s2 return true if s1 < s2

{
     if(isIntString(s1) && isIntString(s2)) 
         return (Integer.parseInt(s1) < Integer.parseInt(s2));
     else
         return (s1.compareTo(s2) < 0);
}

Share this post


Link to post
Share on other sites
Slight update to the code


public int insertInOrder(String input_item)
{
int i,j,insertPos;
if(current_size>0)
{
int conversion = Integer.parseInt(input_item);
for(i=current_size;i>conversion;i--)
tmp[i+1]=data[i];
for(j=0;j<=current_size+1;j++)
{
if(data[j] != null)
{
if(Func.lessThan(input_item,data[j]))
{
data[j]=input_item;
break;
}
else if(input_item.equals(data[j]))
{
data[j+1]=input_item;
break;
}
}
else
{
data[j]=input_item;
break;
}

}
current_size++;
}
else
{
data[0] = input_item;
current_size++;
}

return current_size;
}

Share this post


Link to post
Share on other sites
quote:

I have a program which generates a random list of numbers, and is supposed to insert the numbers into the list in order.


So why the fuss? Use the STL. If you're trying to do what I think you're trying to do, something like this:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

int main() {
typedef std::vector<int>::size_type size;

std::cout << "Number of random numbers: ";
size num;
std::cin >> num;

std::cout << "Maximum random number: ";
size_t max;
std::cin >> max;

srand( static_cast<unsigned>( time(0) ) ); // seed `rand'

std::vector<int> rand_nums;
// could instead use `std::generate' with a random number generator functor here

for (size i = 0; i < num; ++i)
rand_nums.push_back( rand() % max ); // insert rand #


std::sort(rand_nums.begin(), rand_nums.end()); // sort ascending


std::copy( rand_nums.begin(), rand_nums.end(),
std::ostream_iterator<int>(std::cout, "\n") ); // print to standard output (screen)


return 0;
}


[ Google || Start Here || ACCU || STL || Boost || MSDN || GotW || CUJ || MSVC++ Library Fixes || BarrysWorld || E-Mail Me ]

[edited by - Lektrix on October 16, 2003 11:00:02 AM]

Share this post


Link to post
Share on other sites
quote:
So why the fuss? Use the STL.

Well, I think he is using Java.

Do you have to use a list? A binary search tree would be perfect for this.

[edited by - CodeMunkie on October 16, 2003 11:06:28 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yeah STL would do this automatically, but of course that looks like Java code.

However, one question remains... why don''t you do you homework without cheating?

Share this post


Link to post
Share on other sites
**hijacks thread**

std::sort(rand_nums.begin(), rand_nums.end()); // sort ascending

Now how do you insert numbers so as to preserve the order? binary search?
Is it better to use the list?
Or should I write my own tree?

Share this post


Link to post
Share on other sites
quote:
Original post by aboeing
Now how do you insert numbers so as to preserve the order?


You would have to use a sorted associative container, for example std::set, for this type of behaviour. With an associative container, for example std::vector in this case, you''d have to use std::sort to sort the elements after you''ve finished inserting.
quote:
Original post by aboeing
Is it better to use the list?


In this case, probably yes, as std::sort will performing copying. For sorting a list, you would use std::list''s sort method.

[ Google || Start Here || ACCU || STL || Boost || MSDN || GotW || CUJ || MSVC++ Library Fixes || BarrysWorld || E-Mail Me ]

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Yeah STL would do this automatically, but of course that looks like Java code.

However, one question remains... why don''t you do you homework without cheating?


If I were cheating I would have just gone ahead and asked you to write it for me, however I have attempted it. And now although there were some responses in here which were useful(thanks btw) , I have sorted this problem out myself. So asking for a little outside help when I come to a dead end after my attempt, is NOT in my books cheating!!!

Share this post


Link to post
Share on other sites