Solved

Sorting

Posted on 2003-12-01
12
513 Views
Last Modified: 2008-02-01
Hello,

I'm trying to test the insertionSort, quickSort, and mergeSort but I'm getting compilation errors on parts of my program.  Below are the two methods (I think...) that are giving the errors:
-----------------------------------------------------------

private static void choosePivot(Comparable[] theArray, int first, int last) {

      int pivotIndex;
      int mid = (first + last)/2;
            if (theArray[first] <= theArray[mid]) {
                  if (theArray[mid] <= theArray[last]) {
                       pivotIndex = mid;
                  }
                  else {
                       pivotIndex = (theArray[first] <= theArray[last] ? last:first);
                  }
            }
            else if(theArray[last] <= theArray[mid]) {
                 pivotIndex = mid;
            }
            else {
                 pivotIndex = (theArray[first] <= theArray[last] ? first:last);
                 swap(theArray[first], theArray[pivotIndex]);
            }

}  // end choosePivot

//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//*//

 public void swap(int left, int right) {

         Comparable temp = theArray[left];
         theArray[left] = theArray[right];
         theArray[right] = temp;

 } // end swap()

-----------------------------------------------------

Can someone also explain what 'Comparable' is and what it does... because I get the following compilation errors:

operator <= cannot be applied to java.lang.Comparable,java.lang.Comparable  
                        - and -
swap(int,int) cannot be applied to (java.lang.Comparable,java.lang.Comparable)

----------------------------------------------------

Also, the compiler's complaing that it can't find 'theArray' in my swap method:

cannot resolve symbol: Comparable temp = theArray[left];
                                                                     ^

----------------------------------------------------

If you need the rest of my program, please let me know.  Thanks :)
0
Comment
Question by:luna621
  • 7
  • 5
12 Comments
 
LVL 92

Expert Comment

by:objects
ID: 9856193
Comparable is an interface that defines how to compare objects.
It includes one method:
int compareTo(Object o)
See the javadoc for more details.

in your case to use it, instead of:
 if (theArray[first] <= theArray[mid]) {
you would do:
 if (theArray[first].compareTo(theArray[mid])<=0) {
0
 
LVL 92

Expert Comment

by:objects
ID: 9856202
> cannot resolve symbol: Comparable temp = theArray[left];

You need to pass theArray to your swap() method.

public void swap(int[] theArray, int left, int right) {
0
 

Author Comment

by:luna621
ID: 9856767
Yay!  It worked for the swap method, but how do I ".compareTo" for these?  Someone told me to write the ? : form, but I don't understand what that is... can you please explain?  
------------------------------------------------------------------------------------
            else {
            pivotIndex = (theArray[first] <= theArray[last] ? last:first);
            }
      }
      else if(theArray[last].compareTo(theArray[mid])<=0) {
            pivotIndex = mid;
      }
      else {
            pivotIndex = (theArray[first] <= theArray[last] ? first:last);
            swap(theArray[first], theArray[pivotIndex]);
      }

-----------------------------------------------------------------------------------

I also get this error:

swap(java.lang.Comparable[],int,int) cannot be applied to (java.lang.Comparable,java.lang.Comparable)

swap(theArray[first], theArray[pivotIndex]);

What does that mean?  Thank you!
0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
LVL 92

Expert Comment

by:objects
ID: 9856815
> pivotIndex = (theArray[first] <= theArray[last] ? last:first);

pivotIndex = (theArray[first].compareTo(theArray[last])<=0 ? last : first);

> swap(java.lang.Comparable[],int,int) cannot be applied to (java.lang.Comparable,java.lang.Comparable)

you need to pass the array as you have now added it as a param
you also should be passing the index not the array value

swap(theArray, first pivotIndex);
0
 

Author Comment

by:luna621
ID: 9864738
Yay!  It worked!  Okay, but now I'm testing the program.  Is there a way I can have random integers and Strings sorted through my program?  Is there a way to time how long it takes?

Here's my main method so far...
---------------------------------------

      public static void main(String args[]){

            long start = System.currentTimeMillis();
            Date startTime = new Date(start);

            System.out.println(startTime.toString());

//-------------------------------------------
// start testing... need to input random
// numbers and integers here.
//-------------------------------------------



            long stop = System.currentTimeMillis();
            Date stopTime = new Date(stop);

            System.out.println(stopTime.toString());


//-------------------------------------------
// find out how much time spent...
//-------------------------------------------

            Date totalTime = (stopTime - startTime);

      } // end main()

-------------------------------------------------

I seem to have a problem with this line:  Date totalTime = (stopTime - startTime);

It's giving me this error:  operator - cannot be applied to java.util.Date,java.util.Date

-------------------------------------------------

I believe this is the compacted version of something...

pivotIndex = (theArray[first] <= theArray[last] ? last:first);

Is there another way to write the above (without the question mark, etc.)?

-------------------------------------------------

Sorry for asking so many questions.  This is like a 3-in-1 question!  To be fair, I increased the points :)

-luna621 =^_^=

0
 
LVL 92

Accepted Solution

by:
objects earned 350 total points
ID: 9864764
> Date totalTime = (stopTime - startTime);

startTime and stopTime are longs, it should be:

long totalTime = (stopTime - startTime);

> pivotIndex = (theArray[first] <= theArray[last] ? last:first);
> Is there another way to write the above (without the question mark, etc.)?

Its called a ternary operator: <condition> ? <value> : <value>
It is equivalent to:

if (theArray[first] <= theArray[last])
{
   pivotIndex = last;
}
else
{
   pivotIndex = first;
}
0
 

Author Comment

by:luna621
ID: 9871890
Is there a way for me to have RANDOM integers read into the different sort methods?  Can I do the same for Strings?  Do I need to import anything (i.e. import java.util.*;)?
0
 
LVL 92

Expert Comment

by:objects
ID: 9871932
java.util.Random can be used for generating Random numbers.
0
 

Author Comment

by:luna621
ID: 9872031
I want to do something like this in my main to compare the execution times of each sorting method:

- Timings of insertionSort, quickSort, & mergeSort -

 Number of (random) elements: #####

insertionSort execution time in millisecs: #####
     quickSort execution time in millisecs: #####
   mergeSort execution time in millisecs: #####

----------------------------------

How would I make it sort the random ints & Strings?  My insertionSort method is:

public static void insertionSort(Comparable[] theArray, int n) {
...
}

Do I write it like this: insertionSort(???, Math.random());

I don't know what to put for the ??? part.  Because the method calls for a Comparable[] theArray... am I suppose to make an array with random ints?  How do I make that Comparable?
0
 
LVL 92

Expert Comment

by:objects
ID: 9872053
You create your array to sort and then fill it with random numbers using Random.

arr = new Comparable[10];
for (int i=0; i<arr.length; i++)
{
   arr[i] = new Integer(myrandom.nextInt());
}
insertionSort(arr, arr.length);
0
 

Author Comment

by:luna621
ID: 9872696
I think I got it!  Thank you very much!

-luna621 =^_^=
0
 
LVL 92

Expert Comment

by:objects
ID: 9872722
0

Featured Post

3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
varialbe initialization 11 33
eclipse apache tomcat admin console 52 97
Configure a Bean in an XML file 4 32
How do I remove an object from a 3 27
For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question