Super Simple Reverse Sorting

Problem:  Implement Reverse Super Simple Sort -- a sorting algorithm which works by repeatedly finding the largest remaining element and swapping that with its order in the array.


void reverseSuperSimpleSort(int a[]) {
...
}


Solution:  Let's make sure that we understand this algorithm before we start implementing it.


So, assume we have a sample array with the numbers:


10 8 -5 20 9


To sort this array, we would start in the first position and find the biggest number, 20 in this case.  We would then swap 20 with the first number 10, to get:


20 8 -5 10 9


We then move up our iterator and find the largest of the remaining four numbers.  This is 10.  Then, we swap 10 and 8 and get


20 10 -5 8 9


We continue in this way until we get:


20 10 9 8 -5


This is a very simple sorting algorithm, but let's implement it.  We'll write a helper function first which can do the first part of this function -- find the index of the largest element in an array of a known size:


int indexOfLargest (int a[], int arraySize) {
    int indexLargest, maxSoFar, i;


    /*Check the error case */
    if (arraySize <= 0) return ERROR;


    /* initialize maxSoFar and its index to the first element */
    maxSoFar = a[0];
    indexLargest = 0;


    for (i = 1; i < arraySize; i++) {
        if (a[i] > maxSoFar) {
            maxSoFar = a[i];
            indexLargest = i;
        }
    }
    return indexLargest;
}
        





/*Now, we can write the function which does the sorting */
void reverseSuperSimpleSort(int a[]) {
    int i, swapIndex, temp;
    
    for (i = 0; i < a.size -1; i++) {
        swapIndex = indexOflargest(a + i * sizeof(int), a.size - i);
        temp = a[i];
        a[i] = a[i + swapIndex];
        a[i + swapIndex] = temp;
    }
}


That's it!


Let's check this on our original array.  Go through the numbers, and yup, it works.


So, this is a correct solution.  What is the run time? 


Well, the first function, indexOfLargest(), iterates through the entire array that it is given. So this function goes: n + (n-1) + (n-1)...


This is an O(n^2) function.  It's not a super fast sorting algorithm, but it's pretty simple and intuitive.  


/* Please let me know if you find any bugs or alternative solutions.  Thanks, Noah */