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

ClaudeWalkerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

SuperdaveCommented:
The main problem is that you're only dealing with half the array.  You set N to half the length and reference it in a lot of subscripts, but always subtracting from it.  I think you mean to use A.length in those subscript calculations.  Although, if you just used A[j] instead of A[A.length-j] it might be more efficient in terms of cache hits, which is the only real advantage I see in your method.  Otherwise, you're basically just unrolling the loop in a complicated way, which would be a very small benefit.

Also if I understand correctly what you're trying to do, the increment in line 8 should be k+=2 to count the beginning and ending values that you've already dealt with.

Both the nomal selection and max-and-min-at-the-same-time version are O(n^2).
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
phoffricCommented:
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!)
0
SuperdaveCommented:
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.

0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

phoffricCommented:
I need to remember to refresh the screen before I post - lol !!
0
ClaudeWalkerAuthor Commented:
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

0
ClaudeWalkerAuthor Commented:
"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!!!!!
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.