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

}

What you need to ask yourself is: "How many comparisons are done on average". For example, when searching for the largest number in an array going from left to right, the average number of checks will be half the list length. — keyser
– keyser, Commented Mar 27, 2013 at 18:37
Sounds a bit like selection sort. On the nth iteration of the outer loop, the first n elements of the list are in their correct positions. Yours performs more swaps, though. In selection sort, only one swap is performed per outer-loop-iteration. — Kevin
– Kevin, Commented Mar 27, 2013 at 18:38

comingstorm · Accepted Answer · 2013-03-27 22:35:00Z

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.

why not read Wikipedia:Sorting algorithms or download the relevant chapter of Knuth's Fundamental Algorithms?

Alex Shesterov · Accepted Answer · 2013-03-27 19:13:54Z

1

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

answered Mar 27, 2013 at 19:13

Alex Shesterov

27.9k14 gold badges92 silver badges110 bronze badges

Comments

Young Bob · Accepted Answer · 2013-03-27 19:08:04Z

@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).

Collectives™ on Stack Overflow

Sorting algorithm efficiency/performance

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related