Modifying selection sort algorithm

[Jack Sam]

Hi everyone, I was trying to improve my method and I tried everything to fix what was the problem with my method but I can't figure out what is wrong with it. I'm modifying selection sort by not just finding the minIndex and also the maxIndex than swap the minIndex to the left of the array index and the maxIndex with the right side and so on. Could someone look at my method and give me any feedback please? thanks

public  void selectionSort2(String[ ] data){
	
    	for (int place=0; place<data.length-1; place++){
    		int minIndex = place;
    		int maxIndex = place;
    		int rightPlace = data.length-1-place;
    		if (place >= rightPlace) break;
    		for (int sweep=place+1; sweep<rightPlace; sweep++){
    			if (data[sweep].compareTo(data[minIndex]) < 0)
    				minIndex=sweep;
    			if (data[sweep].compareTo(data[maxIndex]) > 0)
    				maxIndex = sweep;
    		}
    		swap(data, place, minIndex);
    		if ( place == maxIndex){
    			maxIndex = minIndex;
    		}
    		swap(data, rightPlace, maxIndex);
    	}
    }	

P.S: my swap method is fine you don't have to worry about it

[Winston Gutkowski]

Jack Sam wrote:Could someone look at my method and give me any feedback please? thanks

Right, I assume that what you're trying to do is to get your selection sort to determine the minimum and maximum remaining values on each pass, correct?

First, your outer loop looks wrong because it will theoretically execute data.length times, when in fact you only need to execute data.length/2 times; which is why you have to include a break statement. Have a think how you might write it so that you don't need that break.

Second: The business of finding the minimum and maximum values is independent of what you want to do with them (ie, swap), so my advice would be to remove that function to a separate method, for example:

// returns the indexes of the minimum AND maximum values of a range
public static final <T extends Comparable<? super T>> int[] minMax(
   int start, int end, T[] values) // 'end' is exclusive
{
   T minValue, maxValue;
   int minIndex, maxIndex;
   minValue = maxValue = values[start];
   minIndex = maxIndex = start;
   for(int i = start+1; i < end; i++) {
      T value = values[i];
      if(value.compareTo(minValue) < 0) {
         minValue = value;
         minIndex = i;
      } else if(value.compareTo(maxValue) > 0) {
         maxValue = value;
         maxIndex = i;
      }
   }
   return new int[] {minIndex, maxIndex};
}

The T stuff is just to make it generic, so it can be used with with any Comparable type. If you don't follow it at the moment, just replace all the T's with String and remove the '<T extends Comparable<? super T>>' altogether.
You'll also notice that I made the 'end' index exclusive. It's not required, but when dealing with ranges you'll find that it makes a lot of things easier. If you look at foundation class methods that deal with ranges (eg, String.subString()) they almost always follow this pattern.

Do you see how a method like that might simplify your sorting loop?

HIH

Winston

PS: Welcome to JavaRanch.

[Winston Gutkowski]

Just one other thing:

There are two conditions that you need to watch out for:
1. An array with an odd number of elements.
2. The situation where ALL remaining elements have the same value.

Winston