asked on

Optimizing a selection sort

I have a selection sort that I am trying to optimize. I am trying to start at both the begining and the end then cycle through all of the values in between. Take the min and max of those values and put them on the ends. Then I increment the begining place holder and decrement the ending one.

This will reduce the complexity from 2N to 3N/2. It will keep the same amount of datamoves and cut down on the comparisons in the process.

Any idea's on why mine is not sorting properly? I'm posting in Java and C++ because this is more of a theory question than a syntax question.

Thanks,
JOe K.

This is my attempt at this MinMax Sort (selection sort at both ends).

public static <E extends Comparable<E>> void twoWaySelectSort(E[] A) { 
	int j, k, minIndex, maxIndex;
	E min, max;
	int N = A.length/2;
	//Cycles to the mid point of the array
	for (k = 0; k < N; k++) {
		//sets the max and min values to the end of the array
		max = A[N-k];
		min = A[k];
		minIndex = k;
		maxIndex = N-k;
		//cycles through the unsorted middle of the array
		for (j = k+1; j < N; j++) {
			//compares the beginning and ends of the unsorted portion 
			if (A[j].compareTo(A[N-j]) > 0){
				//compares the min of the unsorted portion to the overall min
				if (A[N-j].compareTo(min) < 0) {
					dataMove++;
					min = A[N-j];
					minIndex = N-j;
				}
				//compares the max of the unsorted portion to the overall max
				if (A[j].compareTo(max) > 0) {
					dataMove++;
					max = A[j];
					maxIndex = j;
				}
			}else{
				if (A[j].compareTo(min) < 0) {
					dataMove++;
					min = A[j];
					minIndex = j;
				}
				if (A[N-j].compareTo(max) > 0) {
					dataMove++;
					max = A[N-j];
					maxIndex = N-j;
				}
			}
			
		}
		//puts the mins and maxes at the end and then the unsorted bounds are moved
		A[minIndex] = A[k];
		A[k] = min;
		A[maxIndex] = A[N-k];
		A[N-k] = max;	       
	}



Just in case this is helpful this is the code for a working selection sort:


public static <E extends Comparable<E>> void selectionSort(E[] A) {

	int j, k, minIndex;
	E min;
	int N = A.length;
	for (k = 0; k < N; k++) {
		min = A[k];
		minIndex = k;
		for (j = k+1; j < N; j++) {
			if (A[j].compareTo(min) < 0) {
				min = A[j];
				minIndex = j;
			}
		}
		A[minIndex] = A[k];
		A[k] = min;	        
	}

}

Open in new window

ASKER CERTIFIED SOLUTION

Superdave

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

phoffric

Hi,
I see that you have no posts yet, so I have some suggestions.

1. >> I'm posting in ... C++
I don't see the C++ code. I suggest that you post it. You can post both Java and C++ to get assistance from a number of different viewpoints.

2. >> this is more of a theory question than a syntax question
OK, but..

3. >> why mine is not sorting properly?
Then this may be a syntax question rather than an optimization question. I suggest that you post your test drivers and full code (that is fully compilable and runnable). Then we can determine whether you have a syntax error, or a logic error, or a major theory error.

4. >> Optimizing a selection sort
This is a different question than 3 - optimization.

So, my suggestion is that you delete this question, and ask in a new question item 3. After getting your sort to be functionally correct, then post the working code as a separate question and ask about the optimization question.

If you post only Java code, then include one of the Java zones. If you post C++ code, include the C++ Programming Language zone.

(Hah, watch - I bet within a few minutes of this post, someone comes in with a good solution. Hope that happens!)

Superdave

Never mind the k+=2, now that I've thought about it--dividing the length by two takes care of that. On the other hand, if you set N to A.length and used k+=2 for the increment, the other problems would mostly take care of themselves--you could leave the N-j subscripts.

phoffric

I need to remember to refresh the screen before I post - lol !!

ClaudeWalker

ASKER

It works!!!!

@superDave:

I think I only have to increment by one because I am only going to half the array size therefore when I use j and A.length-j that is moving forward and backward so a single increment is appropriate.

The A.length theory is right. I definitely missed that.

I really really really appreciate your help. These things can be maddening without a second set of eyes.

@phoffric:

I didn't realize there was a theory/algorithms section. I'm glad the mod moved it to the right place.

That's a good idea putting it in C++ and Java, I'll give that a shot next time.

You're right about the question header. That was a bit misleading as I posted the goal of my method as opposed to the problem I was facing.

Thanks for the suggestions,
JOe K.

public static <E extends Comparable<E>> void twoWaySelectSort(E[] A) { 
		int j, k, minIndex, maxIndex;
		E min, max;
		int N = A.length/2;
		int subTractor = A.length-1;
		for (k = 0; k < N; k++) {
			max = A[subTractor-k];
			min = A[k];
			minIndex = k;
			maxIndex = subTractor-k;
			for (j = k+1; j < N; j++) {
				if (A[j].compareTo(A[subTractor-j]) > 0){
					if (A[subTractor-j].compareTo(min) < 0) {
						dataMove++;
						min = A[subTractor-j];
						minIndex = subTractor-j;
					}
					if (A[j].compareTo(max) > 0) {
						dataMove++;
						max = A[j];
						maxIndex = j;
					}
				}else{
					if (A[j].compareTo(min) < 0) {
						dataMove++;
						min = A[j];
						minIndex = j;
					}
					if (A[subTractor-j].compareTo(max) > 0) {
						dataMove++;
						max = A[subTractor-j];
						maxIndex = subTractor-j;
					}
				}

			}
			dataMove += 4;
			A[minIndex] = A[k];
			A[k] = min;
			A[maxIndex] = A[subTractor-k];
			A[subTractor-k] = max;	       
		}

Open in new window

ClaudeWalker

ASKER

"Never mind the k+=2, now that I've thought about it--dividing the length by two takes care of that. On the other hand, if you set N to A.length and used k+=2 for the increment, the other problems would mostly take care of themselves--you could leave the N-j subscripts."

I think I only have to increment by one because I am only going to half the array size therefore when I use j and A.length-j that is moving forward and backward so a single increment is appropriate.

Thanks a ton!!!!!