Of course these answers may not get 5/5 as this is from my memory of selection sort from one of last year's Java modules.
The selection sort algorithm is an algorithm that takes the middle of a PRESORTED set/array to try and see where a number should go, or the location of the number if the number is already in the set/array.
My pseudo-code tends ro be closer to C or java code at times, I find it easier to implement it in code that way personally.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
2 | 4 | 5 | 7 | 8 | 11 | 13 | 15 | 21 | 30 |
0 | 1 | 2 | 3 |
---|---|---|---|
2 | 4 | 5 | 7 |
0 | 1 |
---|---|
2 | 4 |
Each of the elements are added in until rValue->newset looks like this:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
2 | 3 | 4 | 5 | 7 | 8 | 11 | 13 | 15 | 21 | 30 |
return rValue
SelectionSort(int set[], int size, int number){
int i;
int greater;
int k;
int b;
//There would be an enum & structin my header for below, just not implemented in the pseudo-code.
rValue->return_code = added;
k = size - 1;
k /= 2;
while(i >= 0 && i < size){
i = k;
if(number == set[i]){
rValue->location = i;
rValue_code->return_code = number_already_in_set;
break;
} else if(number > set[i]){
j = size - i;
j /=2;
k = i + j;
greater = 1;
} else {
k = i / 2;
greater = 0;
}
}
if(greater){
i += 1;
}
if(rValue->return_code != number_already_in_set){
b = 0;
for(int a = 0; a < (size + 1); a++){
if(a == i){
rValue->new_set[a] = number;
} else {
rValue->new_set[a] = set[b];
b += 1;
}
}
}
rValue->number_locateion = i;
return rValue;
}
typedef enum{
number_added,
number_already_in_set
}selectSortRCodes;
typedef struct{
selectSortRCodes return_code;
int location;
int newSet[10000]; //10000 was chosen arbitrarily to allow a large set of numbers be used, may be changed later
}selectSortRValue;
selectSortRValue *selectSort(int set[], int size, int number){
selectSortRValue *rValue = malloc(sizeof(selectSortRValue));
if(rValue != NULL){
int i = 0;
int b;
int j;
int greater;
int k = size - 1;
k /= 2;
while(i >= 0 && i < size && k > 0){
i = k;
if(number == set[i]){
rValue->return_code = number_already_in_set;
break;
} else if(number > set[i]){
j = size - i;
j /= 2;
k = i + j;
greater = 1;
} else {
k = i / 2;
greater = 0;
}
}
if(greater){
i += 1;
}
if(rValue->return_code != number_already_in_set){
b = 0;
for(int a = 0; a < (size + 1); a++){
if(a == i){
rValue->newSet[a] = number;
} else {
rValue->newSet[a] = set[b];
b += 1;
}
}
}
rValue->location = i;
}
return rValue;
}
Selection sort does not work at all with a random array as it is relying on the fact that all numbers in indexes less than the midpoint of the set/array are less than the number at the midpoint and that all numbers to the right of the midpoint of the array are greater than the number at the index of the midpoint. Therefore, Mergesort is more efficient for random arrays. But for arrays with only one number out of place Selection sort is more efficient as once we know where the item is we can gauge where it should be based on the midpoints of each selection (bigger or smaller). Worst case Big O notation for each:
Selection Sort | Mergesort |
---|---|
n^2 | n * log(n) |
Based on the above figures, Mergesort is better though in practice Selection sort will be better for sizes of N less than 100.