2021 Q4 Algorithm

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.

a) explain in plain English the Selection sort algorithm

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.

b) Provide a pseudo-code representation of your Selection sort algorithm.

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.

rough work

0 1 2 3 4 5 6 7 8 9
2 4 5 7 8 11 13 15 21 30

pre-loop:

Loop1 through 1:

0 1 2 3
2 4 5 7

Loop1 through 2:

0 1
2 4

Loop1 through 3:

Post-Loop

Pre-Loop2

Loop2 through 1

Loop2 through 2

Loop2 through to end

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

Post-Loop2

return rValue

Answer

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

c) Provide an implementation of your Selection Sort algorithm for the C programming Language

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

d) Compare the effeciency of Selection sort and Mergesort for: 1. A random Array 2. A pre-sorted array with single element out of order

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.