I'm a beginner in programming and was just playing with sorting and made this algorithm. It is similar to bubble, but it compares not the adjacent pairs but pairs like: first and second, first and third.... second and third, second and fourth and so on. Could you tell me what is the performance/efficiency of the algorithm or compare it to bubble? Or at least advice me on how to solve the problem myself. I'm interested in how much bubble is better than this one. Thank you.
void sortArray(int a[]) {
int q, x, temp;
for ( q = 0; q < SIZE - 1; q++ ) {
for ( x = q + 1; x < SIZE; x++ ) {
if (a[q] < a[x]) {
temp = a[q];
a[q] = a[x];
a[x] = temp;
}
}
}
}
Your sort is similar to classic bubble sort, and should have essentially the same performance.
Both your sort and bubble sort can be viewed as inefficient versions of selection sort. For all three algorithms, each pass of the inner loop iterates through the unsorted region of an array, finds the smallest/largest element, and leaves it in its final location. The algorithms are not identical, because they perform different permutations on the unsorted region -- however, this difference does not contribute functionally to the operation of the algorithm.
Once you recognize this, it is easy to see why selection sort tends to have a constant-factor advantage over the other two: each pass of its inner loop does the minimum number of swaps needed (i.e., one, at the end). By contrast, bubble sort and your sort may end up doing as many as one swap per iteration of the inner loop...
Asymptotically, though, all three sorts will take O(N^2) time -- specifically, there will be N*(N-1)/2 iterations of the inner loop.