JAVA HELP...just 2 quick methods

[AKIRA]

ok so for the final exam...i know that we're going to have to code a selection sort and a binary search on an array of integers...

so let's say he gives us 5 3 7 9 1

how would you do a selection sort and binary search for those integers?

thanks in advance

 

[Insano]

Wouldn't you just write the method (I guess you know how), and put in those numbers?

Unless you don't know how to make a selection sort and binary search.

Edit: I'm waiting for a game to start, so I looked it up for you:

Selection Sort

public static int[] selectionSort (int[] r)
{
int i, j, positie, maximum;
int last = r.length-1;
i = last;
while (i>=0) {
positiemaximum = 0;
j = 0;
while (j != i) {
j ++;
if (r[j] > r[positiemaximum]) {
positiemaximum = j;
}
}
maximum = r[positiemaximum];
r[positiemaximum] = r[i];
r[i] = maximum;
i--;
}
return r;
}

Binary Search

public boolean binarySearch (int[] r, int x)
{
boolean gevonden = false;
int a = 0, b = r.length-1;
while (a != b) {
m = (a + b) / 2;
if (x <= r[m]) {
b = m;
}
else { // x > r[m]
a = m + 1;
}
}
gevonden = (r[a] == x);
return gevonden
}

These are basic algorythms as far as I know. Don't you have to prove the complexity?

 

[AKIRA]

Wouldn't you just write the method (I guess you know how), and put in those numbers?

Unless you don't know how to make a selection sort and binary search.

yea that's the problem..i don't really know how to code it...i have an idea of the binary search tho...am i going in the right direction with this?

public int binarySearch( Comparable [ ] a, Comparable x )  {
   int low = 0, high = a.length - 1;
   int mid;
   while( low <= high ){ 
       mid = ( low + high ) / 2;
       if( a[ mid ].compareTo( x ) < 0 )
           low = mid + 1;            // Search upper partition
       else if( a[ mid ].compareTo( x ) > 0 )
           high = mid - 1;           // Search lower partition
       else
           return mid;               // Found
   }
   return NOT_FOUND;                 // NOT_FOUND is defined as -1
}

 

[CyberPitz]

You're missing a semi colon somewhere.

I'll let you figure it out.

 

[Insano]

Look at the edit from my first post. Should be right, although I haven't tried to compile it.

 

[theotherguy]

Binary search looks right. I don't feel like writing the code out for the selection sort, but basically just do this (this will only work if you have a resizable Array like ArrayList): Create a new array. Create an int called minimum which represents the smallest int in the array. Assume that index 0 contains the minimum by setting the int at index 0 as minimum. Loop through the array until you reach the end, comparing minimum to whatever is in each index. If the int in a particular index is less than minimum, make it equal to minimum. Once you've looped through the array, add the int at the index of minimum to the new array, and delete it from the old one. Repeat this until there is nothing left in the original array.

This is a very unconventional algorithm for selection sorts, and if you're using static arrays it would be something much different. Insano's algorithm is guaranteed to work for static arrays.