Sorting algorithm efficiency/performance

Question

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

}

Answer 1

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.

Answer 2

Short answer - your algorithm has complexity O(n²) - just like bubble sort, i.e. the complexity of both algorithms are essentially the same.

Answer 3

@Kevin is right when he says on the nth iteration of the outer loop the first n elements are in their correct position. The conventional bubble sort (comparing and swapping adjacent elements) also does this but it has the advantage that it is also partially sorts other items in the list as it goes along thereby increasing the chances that the list is sorted before all iterations are complete (when no swaps are detected during an outer loop iteration the sort can finish).