***Converting C code to Java***

ug02070

114

Author

October 10, 2005 09:43 AM

If any of you have the time could you possibly help me convert some C code to its equivalent in Java plz, i really dont know much about c at all but have to try and implement a java version of some c code. below i have listed the c code and also what i have done so far, think its ok apart from the init_arguments method. thanks hope this doesnt seem like too much code, but thanks to all of you who take the time to help, greatly appreciated, even if you can just help with a single method that will be great! (as i know there is quite a few lines here) =) C Code first:


/* Program to produce suffix array. */
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#include &lt;unistd.h&gt;
#include &lt;assert.h&gt;

typedef unsigned int boolean;

#define FALSE 0                 /* For boolean expressions */
#define TRUE 1                  /* For boolean expressions */

#define DUMP_STRING_SIZE 40     /* Used for dumping long strings
				   (for debug purposes */

unsigned int Order = 0;         /* Order used for comparison */

void
usage (void)
{
    fprintf (stderr,
	     "Usage: ident_language [options]\n"
	     "\n"
	     "options:\n"
	     "  -o n\tOrder=n\n"
	     );
    exit (2);
}

void
init_arguments (int argc, char *argv[])
{
    extern char *optarg;
    extern int optind;
    int opt;
    boolean order_found;

    /* set defaults */
    order_found = FALSE;

    /* get the argument options */

    while ((opt = getopt (argc, argv, "o:")) != -1)
	switch (opt)
	{
	case 'o':
	    order_found = TRUE;
	    sscanf (optarg, "%u", &Order);
	    assert (Order &gt; 0);
	    fprintf (stderr, "Order = %d\n", Order);
	    break;
	default:
	    usage ();
	    break;
	}

    if (!order_found)
        usage ();
    for (; optind &lt; argc; optind++)
	usage ();
}

void
SA_init_sarray (unsigned int *sarray, unsigned int size)
/* Initializes the suffix array's index. */
{
    unsigned int p;

    for (p = 0; p &lt; size; p++)
      sarray  = p;
}

void
SA_check_sarray (char *string, unsigned int string_size, unsigned int *sarray)
/* Checks that the suffix array is sorted */
{
    unsigned int p, i, prev_i;
    char cc;

    prev_i = sarray [0];
    for (p = 1; p &lt; string_size; p++)
      {
	i = sarray ;

	if (strcmp (string + prev_i, string + i) &gt; 0)
	  {
	    fprintf (stderr, "Error in suffix array at index %d :\n", p);

	    cc = string [prev_i + 40];
	    string [prev_i + 40] = '\0';
	    fprintf (stderr, "position %6d, string = %s\n",
		     prev_i, string + prev_i);
	    string [prev_i + 40] = cc;

	    cc = string ;
	    string  = '\<span class="cpp-number">0</span>';
	    fprintf (stderr, <span class="cpp-literal">"position %6d, string = %s\n"</span>,
		     i, string + i);
	    string  = cc;
	  }

	prev_i = i;
      }
}

<span class="cpp-keyword">static</span> <span class="cpp-keyword">char</span> *SA_String;

<span class="cpp-keyword">int</span>
SA_qsort_compare (<span class="cpp-keyword">const</span> <span class="cpp-keyword">void</span> *index1, <span class="cpp-keyword">const</span> <span class="cpp-keyword">void</span> *index2)
<span class="cpp-comment">/* Comparison function used by qsort. */</span>
{
  <span class="cpp-keyword">int</span> p1, p2, cmp;

  <span class="cpp-comment">/*fprintf (stderr, "Comparing %p with %p\n", index1, index2);*/</span>
  p1 = *((<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *) index1);
  p2 = *((<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *) index2);
  <span class="cpp-comment">/*fprintf (stderr, "Value     %d with %d\n", p1, p2);*/</span>
  cmp = strcmp (SA_String + p1, SA_String + p2);
  <span class="cpp-keyword">if</span> (!cmp)
    {
      <span class="cpp-keyword">if</span> (p1 &amp;gt; p2)
	 <span class="cpp-keyword">return</span> (<span class="cpp-number">1</span>);
      <span class="cpp-keyword">if</span> (p1 &amp;lt; p2)
	 <span class="cpp-keyword">return</span> (-<span class="cpp-number">1</span>);
    <span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;
    }

  <span class="cpp-keyword">return</span> cmp;
}

<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *
SA_make_sarray (<span class="cpp-keyword">char</span> *string, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> string_size)
<span class="cpp-comment">/* Builds the suffix array in memory. */</span>
{
    <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *sarray;

    SA_String = string;

    sarray = (<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *) malloc (string_size * <span class="cpp-keyword">sizeof</span> (<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>));
    SA_init_sarray (sarray, string_size);

    qsort (sarray, string_size, <span class="cpp-keyword">sizeof</span> (<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span>), SA_qsort_compare);

    SA_check_sarray (string, string_size, sarray);

    <span class="cpp-keyword">return</span> (sarray);
}

<span class="cpp-keyword">void</span>
SA_dump_string ( FILE *fp, <span class="cpp-keyword">char</span> *string, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> p, boolean full_dump)
<span class="cpp-comment">/* Dumps the string to FP. */</span>
{
    <span class="cpp-keyword">int</span> cc, len;

    len = strlen (string + p);
    <span class="cpp-keyword">if</span> (full_dump)
        fprintf (fp, <span class="cpp-literal">"position = %d, string = "</span>, p);
    <span class="cpp-keyword">if</span> (len &amp;lt; DUMP_STRING_SIZE)
        fprintf (fp, <span class="cpp-literal">"%s\n"</span>, string + p);
    <span class="cpp-keyword">else</span>
      {
	cc = string [p + DUMP_STRING_SIZE];
	string [p + DUMP_STRING_SIZE] = '\<span class="cpp-number">0</span>';
	fprintf (stderr, <span class="cpp-literal">"%s\n"</span>, string + p);
	string [p + DUMP_STRING_SIZE] = cc;
      }
}

<span class="cpp-keyword">void</span>
SA_dump_sarray (FILE *fp, <span class="cpp-keyword">char</span> *string, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> string_size,
		<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *sarray)
<span class="cpp-comment">/* Dumps out the suffix array to file FP (fro debug purposes). */</span>
{
    <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> p, i;

    <span class="cpp-keyword">for</span> (p = <span class="cpp-number">0</span>; p &amp;lt; string_size; p++)
      {
	i = sarray <p>;
	fprintf (fp, <span class="cpp-literal">"%6d : %6d "</span>, p, i);
	SA_dump_string (fp, string, i, <span class="cpp-keyword">TRUE</span>);
      }
}

<span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> SA_compute_measure
(<span class="cpp-keyword">char</span> *string1, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> string_size1, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *sarray1,
 <span class="cpp-keyword">char</span> *string2, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> string_size2, <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *sarray2,
 <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> order)
<span class="cpp-comment">/* Computes a measure of similarity between the two strings
   using their respective suffix arrays. */</span>
{
    <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> p1, p2, i1, i2, measure;
    <span class="cpp-keyword">int</span> result;

    p2 = <span class="cpp-number">0</span>;
    measure = <span class="cpp-number">0</span>;
    <span class="cpp-keyword">for</span> (p1 = <span class="cpp-number">0</span>; p1 &amp;lt; string_size1;)
      {
	<span class="cpp-comment">/* We are now at the start of a "new" group of prefixes as
	   determined by the Order length */</span>

	i2 = sarray2 [p2];

	<span class="cpp-keyword">if</span> (strlen (string1 + i1) &amp;lt; order)
	    <span class="cpp-keyword">continue</span>;

	<span class="cpp-keyword">while</span> ((result = strncmp (string2 + i2, string1 + i1, order)) &amp;lt; <span class="cpp-number">0</span>)
	  {
	    <span class="cpp-comment">/*
	    fprintf (stderr, "Skipping suffix array at index %d,%d :\n",
		     p1, p2);

	    SA_dump_string (stderr, string1, i1, TRUE);
	    SA_dump_string (stderr, string2, i2, TRUE);
	    */</span>

	    p2++;
	    <span class="cpp-keyword">if</span> (p2 &amp;gt;= string_size2)
	        <span class="cpp-keyword">break</span>;
	    i2 = sarray2 [p2];
	  }

	<span class="cpp-keyword">if</span> (!result) <span class="cpp-comment">/* Prefixes up to length order are equal */</span>
	  {
	    measure++;
	    fprintf (stderr, <span class="cpp-literal">"Prefixes match at index %d,%d :\n"</span>,
		     p1, p2);
	    SA_dump_string (stderr, string1, i1, <span class="cpp-keyword">TRUE</span>);
	    SA_dump_string (stderr, string2, i2, <span class="cpp-keyword">TRUE</span>);
	  }

	<span class="cpp-comment">/* Skip through suffix array 1 until we reach the start of
	   a new group of prefixes */</span>
	old_p1 = p1;
	old_i1 = i1;
	<span class="cpp-keyword">for</span> (;;)
	  {
	    p1++;
	    <span class="cpp-keyword">if</span> (p1 &amp;gt; string_size1)
	        <span class="cpp-keyword">break</span>;
	    i1 = sarray [p1];
	    <span class="cpp-keyword">if</span> ($$$result = strncmp (string1 + old_i1, string1 + i1, order)) &amp;lt; <span class="cpp-number">0</span>)
	  }
	<span class="cpp-keyword">while</span> (
	      {
	      }

	<span class="cpp-comment">/*
	fprintf (stderr, "Position %d,%d :\n", p1, p2);

	SA_dump_string (stderr, string1, i1, TRUE);
	SA_dump_string (stderr, string2, i2, TRUE);
	*/</span>
      }

    <span class="cpp-keyword">return</span> (measure);
}

<span class="cpp-keyword">int</span>
main (<span class="cpp-keyword">int</span> argc, <span class="cpp-keyword">char</span> *argv[])
{
    <span class="cpp-keyword">char</span> string1 [<span class="cpp-number">128</span>], string2 [<span class="cpp-number">128</span>];
    <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> *sarray1, *sarray2,  string_size1, string_size2, measure;

    init_arguments (argc, argv);

    <span class="cpp-comment">/*
    string = (char *) malloc (array_size * sizeof (char));
    sarray = (unsigned int *) malloc (array_size * sizeof (unsigned int));
    */</span>

    <span class="cpp-comment">/* Read in the input file */</span>
    <span class="cpp-comment">/*string_size = fread (string, sizeof (char), array_size+1, stdin);*/</span>

    fprintf (stdout, <span class="cpp-literal">"Enter string1: "</span>);
    fscanf (stdin, <span class="cpp-literal">"%s"</span>, string1);
    string_size1 = strlen (string1) + <span class="cpp-number">1</span>;

    fprintf (stdout, <span class="cpp-literal">"Enter string2: "</span>);
    fscanf (stdin, <span class="cpp-literal">"%s"</span>, string2);
    string_size2 = strlen (string2) + <span class="cpp-number">1</span>;

    sarray1 = SA_make_sarray (string1, string_size1);
    sarray2 = SA_make_sarray (string2, string_size2);

    <span class="cpp-comment">/*dump_sarray (string, string_size, sarray);*/</span>
    measure = SA_compute_measure (string1, string_size1, sarray1,
				  string2, string_size2, sarray2, Order);

    fprintf (stderr, <span class="cpp-literal">"Measure = %d\n"</span>, measure);

    exit (<span class="cpp-number">1</span>);
}

</pre></div><!–ENDSCRIPT–>

================================================
My Java Code So Far:

<!–STARTSCRIPT–><!–source lang="java"–><div class="source"><pre>

<span class="java-keyword">import</span> java.io.BufferedReader;
<span class="java-keyword">import</span> java.io.InputStreamReader;
<span class="java-keyword">import</span> java.io.IOException;

<span class="java-visibilitymodifier">public</span> <span class="java-keyword">class</span> SArray
{
	
	
	<span class="java-comment">// Builds the suffix array in memory</span>
	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">int</span>[] SA_make_sarray(String string, <span class="java-primitives">int</span> stringSize)
	{
		String SA_string;
		<span class="java-primitives">int</span>[] sarray;
		
		<span class="java-comment">//SA_string = aString;</span>
		sarray = <span class="java-keyword">new</span> <span class="java-primitives">int</span>[stringSize];
		
		SA_init_sarray(sarray, stringSize);
		SA_check_sarray(string, stringSize, sarray);
		
		<span class="java-keyword">return</span> sarray;
	}
	
	<span class="java-comment">//Initializes the suffix array's index. </span>
	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">void</span> SA_init_sarray(<span class="java-primitives">int</span>[] sarray, <span class="java-primitives">int</span> size)
	{
		<span class="java-keyword">for</span>(<span class="java-primitives">int</span> p = <span class="java-number">0</span>; p &amp;lt; size; p++)
		{
			sarray<p> = p;
		}	
	}
	
	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">void</span> SA_check_sarray(String string, <span class="java-primitives">int</span> stringSize, <span class="java-primitives">int</span>[] sarray)
	{
		<span class="java-primitives">int</span> p;
		<span class="java-primitives">int</span> i = <span class="java-number">0</span>; 
		<span class="java-primitives">int</span> prev_i = <span class="java-number">0</span>;
		<span class="java-primitives">char</span> cc;
		<span class="java-primitives">char</span>[] charArray = string.toCharArray();
		
		prev_i = sarray[<span class="java-number">0</span>];
		<span class="java-keyword">for</span>(p = <span class="java-number">1</span>; p &amp;lt; stringSize; p++)
		{
			i = sarray<p>;
			<span class="java-keyword">if</span> ((string + prev_i).compareTo((string + i)) &amp;gt; <span class="java-number">0</span>)
	  		{
	    		System.out.println (<span class="java-literal">"Error in suffix array at index : "</span> + p);
	    	}
	    	cc = charArray [prev_i + <span class="java-number">40</span>];
		    charArray [prev_i + <span class="java-number">40</span>] = '\<span class="java-number">0</span>';
		    System.out.println (<span class="java-literal">"position "</span> + prev_i + <span class="java-literal">", string = "</span> + (string + prev_i));
		    charArray [prev_i + <span class="java-number">40</span>] = cc;
	
		    cc = charArray ;
		    charArray  = '\<span class="java-number">0</span>';
		    System.out.println (<span class="java-literal">"position "</span> + i + <span class="java-literal">", string = "</span> + (string + i));
		    charArray  = cc;
	 	}
	
		prev_i = i;
	}
	
	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">void</span> init_arguments (String args[])
	{
	    <span class="java-primitives">char</span> optarg = '?';
	    <span class="java-primitives">int</span> optind;
	    <span class="java-primitives">int</span> opt = <span class="java-number">0</span>;
	    <span class="java-primitives">boolean</span> order_found;
	
	    <span class="java-comment">/* set defaults */</span>
	    order_found = <span class="java-keyword">false</span>;
	
	    <span class="java-comment">/* get the argument options */</span>
	
	    <span class="java-keyword">while</span> (opt != -<span class="java-number">1</span>)
	    {
	    	opt = args.toString().indexOf(<span class="java-literal">"o:"</span> + <span class="java-number">1</span>);
	    }
		<span class="java-keyword">switch</span> (opt)
		{
			<span class="java-keyword">case</span> 'o':
			    order_found = <span class="java-keyword">true</span>;
			    <span class="java-comment">//sscanf (optarg, "%u", &amp;Order); get integer out of optarg and place in Order</span>
			    <span class="java-primitives">int</span> Order = optarg;
			    <span class="java-keyword">if</span> (Order &amp;gt; <span class="java-number">0</span>)
			    {
			    	System.out.println(<span class="java-literal">"Error, order greater than <span class="java-number">0</span>…Exiting"</span>);
			    	System.exit(<span class="java-number">0</span>);	
			    }
			    System.out.println(<span class="java-literal">"Order = "</span> + Order);
			    <span class="java-keyword">break</span>;
			<span class="java-keyword">default</span>:
			    usage ();
			    <span class="java-keyword">break</span>;
		}
	
	    <span class="java-keyword">if</span> (!order_found)
	        usage ();
	    <span class="java-comment">//for (; optind &amp;lt; args; optind++)</span>
		<span class="java-comment">//usage ();</span>
	}

	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">void</span> usage()
	{
	    System.out.println(<span class="java-literal">"Usage: ident_language [options]\n"</span>);
	    System.out.println(<span class="java-literal">"options:\n"</span>);
		System.out.println(<span class="java-literal">"-o n\tOrder=n\n"</span>);
	    System.exit(<span class="java-number">0</span>);
	}


	
	<span class="java-visibilitymodifier">public</span> <span class="java-storageclasses">static</span> <span class="java-primitives">void</span> main (String args[]) <span class="java-keyword">throws</span> IOException
	{
	    String string1; 
	    String string2; 
	    <span class="java-primitives">int</span>[] sarray1, sarray2;
	    <span class="java-primitives">int</span> string_size1, string_size2, measure;
	
	    init_arguments (args);
	
	    <span class="java-comment">/*
	    string = (char *) malloc (array_size * sizeof (char));
	    sarray = (unsigned int *) malloc (array_size * sizeof (unsigned int));
	    */</span>
	
	    <span class="java-comment">/* Read in the input file */</span>
	    <span class="java-comment">/*string_size = fread (string, sizeof (char), array_size+1, stdin);*/</span>
	    
	    BufferedReader br = <span class="java-keyword">new</span> BufferedReader(<span class="java-keyword">new</span> InputStreamReader(System.in));
	
	    System.out.println(<span class="java-literal">"Enter string1: "</span>);
	    string1 = br.readLine();
	    string_size1 = string1.length() + <span class="java-number">1</span>;
	
	    System.out.println(<span class="java-literal">"Enter string2: "</span>);
	    string2 = br.readLine();
	    string_size2 = string2.length() + <span class="java-number">1</span>;
	
	    sarray1 = SA_make_sarray (string1, string_size1);
	    sarray2 = SA_make_sarray (string2, string_size2);
	}
}

</pre></div><!–ENDSCRIPT–> 

<!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - ug02070 on October 10, 2005 10:17:26 AM]<!–EDIT–></span><!–/EDIT–>

TDragon

679

October 10, 2005 09:50 AM

Before I even try figuring any of that out, might I recommend reformatting your post to use the neat-o source code formatting? For C code, use [source lang="c"](code here)[/source]; for Java code, use [source lang="java"](code here)[/source].

Thanks,
Twilight Dragon

{[JohnE, Chief Architect and Senior Programmer, Twilight Dragon Media{[+++{GCC/MinGW}+++{Code::Blocks IDE}+++{wxWidgets Cross-Platform Native UI Framework}+++

ug02070

114

Author

October 10, 2005 10:18 AM

that looks better, thanks!

TDragon

679

October 10, 2005 11:31 AM

Hokay...I got started on it for the heck of it (you're lucky in that respect; I normally don't help people with actual code much), and then realized I didn't know what exactly it was supposed to do. I pasted what I had so far below, in case you're interested.

In any case, there are two things I noted:

First, the plus symbol denotes two separate things in the C version and the Java version of the SA_check_sarray function; specifically, the line "if (strcmp (string + prev_i, string + i) > 0)". In the C version, it increments the memory pointer "string" by the amounts prev_i and i respectively, which in effect makes strcmp see a substring of the string rather than the whole thing. What you have in Java doesn't do that; rather, it concatenates the number onto the end of the string. Not what you want, I'd assume; rather, you need to use the String.substring() function.

Second, the qsort() function is a part of the C Standard Library, and you'll have to find some sort of equivalent in Java or make your own. Collections.sort(), possibly?

Here's what I had so far (please excuse any mistakes, as it's been a few months since I programmed Java):

public class SuffixArray{    static int static_order = 1;    int order;    public SuffixArray(int input_order)    {        order = (input_order > 0) ? input_order : 1; //the check is unnecessary as the program currently stands,                                                     //but good practice for if you ever change it    }    public static void main(String[] args) throws IOException    {        try        {            HandleArgs(args);        }        catch (ParseException e)        {            PrintUsage();            return;        }        //TODO    }    public static void HandleArgs(String[] args) throws ParseException    {        for (int arg_at = 0; arg_at < args.length; arg_at++)        {            if (args[arg_at].equals("-o"))            {                if (arg_at + 1 >= args.length)                    throw new ParseException("-o must be followed by an order.");                arg_at++;                try                {                    static_order = Integer.parseInt(args[arg_at]);                }                catch (NumberFormatException e)                {                    throw new ParseException(args[arg_at] + "is not a valid order input.");                }                if (static_order <= 0)                    throw new ParseException("The order must be greater than 0.");            }            else                throw new ParseException(args[arg_at] + "is not a valid argument.");        }    }}

{[JohnE, Chief Architect and Senior Programmer, Twilight Dragon Media{[+++{GCC/MinGW}+++{Code::Blocks IDE}+++{wxWidgets Cross-Platform Native UI Framework}+++

ug02070

114

Author

October 10, 2005 01:34 PM

nice one, thanks for your help, i'm glad you decided to help someone with code because i dont know c at all.
i shall try working through the rest now,
does anyone know if the qsort method can be done in java, my lecturer reckons that it traverses and compares two trees simultaneously (effectively) and said that he's not sure if this is possible in java, one person tried and failed, he is pretty hard on java so doesnt think it can be done? can anyone prove him wrong?
thanks

Martok

122

October 10, 2005 01:46 PM

Quote:Original post by ug02070
nice one, thanks for your help, i'm glad you decided to help someone with code because i dont know c at all.
i shall try working through the rest now,
does anyone know if the qsort method can be done in java, my lecturer reckons that it traverses and compares two trees simultaneously (effectively) and said that he's not sure if this is possible in java, one person tried and failed, he is pretty hard on java so doesnt think it can be done? can anyone prove him wrong?
thanks

qsort is just the quicksort algorithm if I'm not mistaken, the java container classes most likely have a sorting algorithm, it would surprise me if they hadn't.

And quicksort does not work by comparing 2 trees.

ZQJ

496

October 10, 2005 01:46 PM

I'm pretty sure qsort is a fairly dumb function - just a standard quicksort which will use the comparison function to compare elements and memcpy with a buffer to swap them.

Anyway, what you'll probably be wanting is one of Java's containers instead of an array, although this won't be very efficient for such a simple case. Alternatively you could just write your own quicksort, it's pretty easy and will almost certainly CREAM the C qsort routine for speed.

TDragon

679

October 10, 2005 02:07 PM

Quote:Original post by ug02070
does anyone know if the qsort method can be done in java, my lecturer reckons that it traverses and compares two trees simultaneously (effectively) and said that he's not sure if this is possible in java, one person tried and failed, he is pretty hard on java so doesnt think it can be done? can anyone prove him wrong?

Either your instructor is talking BS or he's being misquoted.

Quicksort is extraordinarily easy to implement in Java for a single basic type. We did it in Data Structures last semester. But I'd suspect you don't even need to implement your own sorting algorithm for this instance; the Java class library has everything you could need and more. See the methods in the Collections class that I mentioned earlier for starters.

Cheers,
Twilight Dragon

{[JohnE, Chief Architect and Senior Programmer, Twilight Dragon Media{[+++{GCC/MinGW}+++{Code::Blocks IDE}+++{wxWidgets Cross-Platform Native UI Framework}+++

kevmo

205

October 10, 2005 02:34 PM

Instead of inserting items into an array and then sorting that array, you can insert into the Java TreeSet collection, which will guarantee that when you create an iterator for the collection, the elements are sorted. Or, you can use the toArray method after inserting everything into the TreeSet, if you must have the data in an array.

If you have taken any sort of algorithm analysis, the TreeSet uses a heap as its underlying data structure, so each insert is O(logN). When you remove elements from a heap, they are guaranteed to be in order by the properties associated with the heap, and each remove-smallest operation is O(logN) as well. Therefore, the entire insert-into-array-and-sort operation is O(NlogN), which is the same complexity as quick sort. Which method is actually faster on average depends on a bunch of different factors, and it is usually easiest to just do an empirical comparison on real data. The advantage to using a heap sort here is ease of coding - the whole thing is just a few lines of code in Java.

Java TreeSet API

sjelkjd

171

October 10, 2005 09:35 PM

Or you could just use Arrays.Sort which probably uses quicksort, will be faster than a tree set, and won't take up extra memory.

Converting C code to Java

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

***Converting C code to Java***

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines

Converting C code to Java