**JAVA QUESTION**

[santana9]

I am trying to write a selection sort that uses a switch statement to determine whether it should be sorted in ascending or descending order. I have timed the process and it is twice the time of the code without the switch statement and even longer then the bubblesort of the same #'s. How can I rewrite this to get back to actual speed...thanx in advance:

public void selectionSort(char sequence)
{
int out, in, min;

for(out=0; out<nElems-1; out++) // outer loop
for(in=out+1; in<nElems; in++) // inner loop

switch (sequence) {

case 'A':
min = out;
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
break;

case 'D':
min = out;
if (a[in] > a[min] )
min = in; // we have a new min
swap(out, min); // swap them
break;

} // end switch
} // end selectionSort()

 

[TheDiggler]

Let me give you a C++ solution which can hopefully be applied to JAVA:

1) Create a PURE VIRTUAL class called ComparatorClass (PURE VIRTUAL is an ABSTRACT class)
[*] Define 1 pure virtual method in this class called "checkValues(int a, int b)" which accepts 2 integers and returns a bool:
[*] bool checkValues(int a, int b) { return false };

2) Define a CHILD CLASS of ComparatorClass called ComparatorAscendingClass
[*] Define and code method "checkValues(int a, int b)" as follows:
[*] bool checkValues(int a, int b) { return (a < b); }

3) Define a CHILD CLASS of ComparatorClass called ComparatorDescendingClass
[*] Define and code method "checkValues(int a, int b)" as follows:
[*] bool checkValues(int a, int b) { return (a > b); }

4) In your selectionSort routine, now do the following:

public void selectionSort(char sequence)
{
int out, in, min;

ComparatorClass myComparator;

if (sequence == 'A') myComparator = new ComparatorAscendingClass();
else myComparator = new ComparatorDescendingClass();

for(out=0; out<nElems-1; out++) // outer loop
for(in=out+1; in<nElems; in++) // inner loop
{
min = out;
if ( myComparator.checkValues(a[in], a[min]) )
{
min = in; // we have a new min
swap(out, min); // swap them
}
}
} // end selectionSort()[/quote]

NOTE: Hite Quote to see the code above formatted a little better.

 

[manly]

I'm not an expert on algorithms, but I'll discuss a couple issues.

First off, one reason why this code is slower is because the switch logic lies in the inner loop. It is being needlessly executed on every pass of the inner loop, which is excess overhead. To optimize this, you should make it a one time test outside of the loop. So the question then becomes, how do you specify behavior inside the loop if your logic test is outside the loop. In Java, you use the Strategy pattern. Basically, the behavior (the sorting inside the inner loop) is wrapped inside an object. I'll let you search Google for implementation advice on the Strategy pattern. This is Java's idiom for function pointers.

Now if you don't want to implement the correct object-oriented solution, you might be able to get lucky with the JIT compiler. Basically, you can try to give a hint to the JIT compiler to optimize away the redundant switch on every loop iteration. In simple terms, the compiler will remove any "dead" code which does not affect the program. To do this, create a local final variable to store the sequence argument:

final char sortOrder = sequence;
// Then switch on sortOrder rather than sequence

Since sortOrder is final, it can't be changed, and an intelligent compiler would strip away the excess code in the inner loop to just the necessary instructions. The only way to know if this will work is to time it. Like I said, you could get lucky.

Finally, I don't think your code would work as shown. In Java, arguments are passed by value (even reference objects). In short, this means you cannot implement a swap() function like you can in other languages. You can swap the elements of an array by passing the array as an argument; but not two variables directly.

 

[santana9]

set final char sortOrder = sequence and it lowered the selection sort time a little bit, but it is still longer then the bubblesort time with the same random #'s.

ps. the swap variables are defined in a seperate class.

 

[santana9]

up

 

[wjsulliv]

I'm a little confused by your code?

The reason your code is slower is because you are swaping every time you find a new min in the inner loop. Selection sort finds the aboslute min of the unsorted section and swaps that with the next element.

Example of your code on [5, 4, 3 ], presuming case 'A':
Start Outer Loop: out = 0
Start Inner Loop: in = 1
Switch = 'A'
min = 5
a[in] = 4
a[in] < a[min] (4<5)
swap -----------------------------> now order looks like this [4, 5, 3]
increment inner loop, in = 2
Switch = 'A'
min = 4
a[in] = 3
a[in] a[min] (3<4)
swap -----------------------------> now order looks like this [3, 5, 4]
increment inner loop, in = 3
increment outer loop out = 1
.....
This algorith take 3 swaps to be sorted. I should take only 2. Selection sort should take at most n-1 swaps to complete sorting and should take n^2 time.


You algorithm should find the min for the unsorted section and then swap...
Outer loop
Inner loop
Switch
find min/max here
end inner loop
swap
end outter loop

like this

public void selectionSort(char sequence)
{
int out, in, min;

for(out=0; out<nElems-1; out++) // outer loop
{
min = out
for(in=out+1; in<nElems; in++) // inner loop
{
switch(sequence){
case 'A'
if(a[in] < a[min])
min = in
break

case 'D'
if(a[in] > a[min])
min = in
break
} // end switch

} // end inner loop

swap(out, min)

} // end outer loop

Running my code on [5, 4, 3] assuming case = 'A'
Start outerloop: out = 0
min = out ------- (min = 0, so min points to a value of 5)
Start inner loop: in = 1
switch ('A')
a[in] = 5
if (4<5) ---------- if is true
min = in --------- (min = 1, so min points to a value of 4)
increment inner loop: in = 2
switch ('A')
a[in] = 3
if (3 < 4) --------- if is true
min = in ---------- (min = 2, so min points to a value of 3)
end inner loop
swap (out, in) ------------- swaps 3 and 5 so A looks like this [3, 4, 5]
increment outer loop: out = 1
min = out -------- (out =1, so min points to a value of 4)
start inner loop: in = 2
if (5 < 4) -------- if is false so do nothing
end inner loop
swap (out, in) -------- swaps 4 with 4 ---------------------------------- ( you could add an if here to test if out = in, as no swap is needed when out = in.
end outer loop

final array [3, 4, 5]

Hope that helps