I have written a modified version of selection sort where I consider both a minimum and maximum of an array and place them at the two ends
The algorithm works like this
1. Find the minimum and the maximum value in the list.
2. Swap the minimum value with the value in the first position.
3. Swap the maximum value with the value in the last position.
4. Repeat the steps above for the remainder of the list
(starting at the second position and ending at the second to
last position and narrowing the range of positions examined
from both ends of the array each time).
Unfortunately the above is showing unexpected results for arrays having duplicates values.
For example,
[9, 37, 12, 1, 13, 31, 5, 37, 36, 29, 19, 22, 20, 15, -1, 23]
was sorted to
[-1, 1, 5, 9, 12, 13, 15, 19, 20, 22, 23, 29, 31, 37, 36, 37]
In fact, the main issue here is that the algorithm in general is not doing proper sorting for the elements in the latter part of the array, besides simply with respect to duplicates.
Here is my pseudocode
int i=0;
while(i<=(arr.length-i-1)) {
int minIndex = i;
int maxIndex=arr.length-i-1;
for (int j = i+1; j <=arr.length-i-1; j++) {
if (arr[j] <=arr[minIndex]) {
minIndex = j;
}
if(arr[j]>=arr[maxIndex]){
maxIndex = j;
}
}
swap(arr, i, minIndex);
swap(arr, (arr.length-i-1), maxIndex);
i++;
}
EDIT This is the swap part of my code which is the only thing that interacts with the algorithm. I don't think it will make any difference but I'll include it anyway
private static void swap(int[] arr, int oldIndex, int newIndex){
int temp=arr[oldIndex];
arr[oldIndex]=arr[newIndex];
arr[newIndex]=temp;
}
The problem happens when i happens to be the maxIndex. To fix that you need to add:
swap(arr, i, minIndex);
if(i == maxIndex) {
maxIndex = minIndex;
}
swap(arr, (arr.length-i-1), maxIndex);