I played with this, using the bubblesort algorithm from Wikipedia, which is a good bubbler, I think.
Code:
#include <stdio.h>
int bubblesort(int n[]);
int main() {
int i, compare;
int n[9] = {9,2,3,6,5,4,7,8,1};
printf("\n\n\n");
compare = bubblesort(n);
printf("\n Comparisons made: %d\n", compare);
for(i = 0; i < 9; i++)
printf("%2d ", n[i]);
printf("\n\t\t\t press enter when ready");
i = getchar();
return 0;
}
int bubblesort(int n[]) {
int i, j, compare, temp, swaps, unsorted;
int topIndex = 9;
compare = swaps = 0;
do {
unsorted = 0;
for(i = 0; i < topIndex - 1; i++) {
//if(order > 0) {
compare++;
// shows the array when there's a comparison being made
//printf("\n i: %d %3d%3d%3d%3d%3d%3d%3d%3d%3d", i,n[0],n[1],n[2],n[3],n[4],n[5],n[6],n[7],n[8]);
//j = getchar();
if(n[i] > n[i+1]) {
temp = n[i];
n[i] = n[i+1];
n[i+1] = temp;
swaps++;
unsorted = 1;
// shows the array when a swap has been made
//printf("\n i: %d %3d%3d%3d%3d%3d%3d%3d%3d%3d", i,n[0],n[1],n[2],n[3],n[4],n[5],n[6],n[7],n[8]);
//j = getchar();
}
//}
}
topIndex--;
}while(unsorted);
printf("\n Swaps: %d \n", swaps);
return compare;
}
/*
This is the bubbler algorithm from Wiki, in pascal
do
swapped := false
for each i in 0 to n - 2 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
n := n - 1
while swapped
*/
I can cheat and make it yield the required 15 comparisons and correctly sort that particular data set however, it's not a correct solver for other number sets (put the 9 at numbers[0], and the 1 at numbers[8] for a good test).
I have an idea for using buckets with this - we'll see how that goes. I define "compare" as any comparison of an array's value, with anything else (including just variables). Or would a comparison only be counted if it compared two array values?
Without changing the algorithm into insertion sort, (or whatever), what could you do to limit the comparisons to their lowest number possible?