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 */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
asdwer
ReplyDelete