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.

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 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;
}
}
```

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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.

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 trialI 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:

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;
}
```

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!!!!!

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.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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-ti