New Modified Selection Sort Algorithm (It outperforms Insertion Sort in some cases) goes like standard Selection Sort Algorithm , but instead searching for only a minimum in an Array , it searches for minimum and maximum in one iteration. Then it swaps minimum to start of an Array and maximum to end of an Array. Increments start_pointer, decrements end_pointer, and then goes iterative again. I think time complexity it needs to sort N size array is : N + (N-2) + (N-4) + (N-6) + ... + 1. Can someone give me approximation of this formula. I will be appreciated.
public static void DoubleSelectionSort(int[] Array, int startpos, int endpos) {
/*Double Selection Sort Algorithm , made by Milan Domonji 1986 , MilanDomonji@yahoo.com*/
while(startpos < endpos) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int minpos = startpos;
int maxpos = endpos;
for(int i = startpos; i <= endpos; i++) {
//main loop that finds minimum and maximum from an Array
if (Array[i] <= min) {
min = Array[i];
minpos = i;
}
if (Array[i] >= max) {
max = Array[i];
maxpos = i;
}
}
/* I added missing part of algorithm so it works now (Edited) */
if (maxpos==startpos && minpos==endpos) {
Swap(Array, minpos, maxpos);
}else {
if (maxpos==startpos) {
Swap(Array,minpos,startpos);
Swap(Array,minpos,endpos);
}else {
Swap(Array,minpos,startpos);
Swap(Array,maxpos,endpos);
}
}
startpos++;
endpos--;
}
}
private static void Swap(int[] Array, int A, int B) {
int tmp = Array[A];
Array[A] = Array[B];
Array[B] = tmp;
}
Algorithm Sorts all the times correctly.
