How to find formula for given sorting algorithm

Isak Midtvedt 0
Viewed 50

Given a function that takes in an array a that compares a[0] and a[1] and if a[0] < a[1] they swap places. The function then keeps comparing the current element with the next one and swaps if it is bigger. This way you are left with the biggest element at the end of your array. How would I go about defining a formula for the average amount of swaps it would take? I understand why Hn is what it is for other sorting algorithms but I am having a hard time understanding how you "calculate" or work your way to what the algorithm is for the given function.

public static int maxB(int[] a) {
    if(a.length < 1)
        throw new NoSuchElementException("empty array");
    for(int i = 1; i < a.length; i++) {
        if(a[i-1] > a[i]) {
            int temp = a[i-1];
            a[i-1] = a[i];
            a[i] = temp;
        }
    }
    return a[a.length - 1];
}

This is the code in quesiton that I have written and I am not asking for coding help or formatting etc. I know it is "bad" and primitive but I just wanted to use this as an example on how to find formulas for the average of a given algorithm and this one is one of the few I dont understand how to do it for. Appreciate the help

array-formulas sorting java algorithm
1 Answers

There is no hard and fast rule to find the performance of an algorithm.

But for this one, let's define an inversion as a pair (x, y) with x < y but a[y] < a[x]. Show that every swap reduces the number of inversions by 1. Also if the array is sorted, there are no inversions. And therefore the number of swaps you need to sort the array is the same as the number of inversions.

Your question therefore becomes, "On average, how many inversions are there?" And the answer is that there are n*(n-1)/2 pairs, and half of them will be inversions on average, for an average of n*(n-1)/4 = O(n^2) inversions.

btilly0
Related