CODEWITHSUNDEEP
ctime-complexitybubble-sort
Jiseong
Jiseong

Reputation: 89

Runtime of Bubble sort algorithms in C

Hi I'm taking a lecture about Data Structure and Algorithm in my college. I'm doing assignment about analyzing sorting algorithm. The assignments require the report that includes measuring run time of algorithm. TA gave us the three datasets of 30000 integers.(ascending order, descending order, random order)

I thought sorting descending order data would take more than sorting randomly ordered data. But in my bubble sort algorithm, the result is opposite.

It takes 2.453s real time and 2.409s user time to sort the numbers in descending order, and 3.217s real time and 3.159s user time to sort the numbers in random order. This result is also about my Selection Sort Algorithm. Isn't the descending ordered number worst case?

//file is opened at main function
int* bubble_prj4(FILE *fp_in)
{
    int i, j, temp;

    //arr is declared in header file
    arr = (int*)malloc(sizeof(int) * 30000);
    fread(arr, sizeof(int), 30000, fp_in);
    for(i = 0; i < 29999; i++)
        for(j = 29999; j > i; j--)
            if(arr[j] < arr[j - 1])
            {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
    return arr;
}

It's my first time to ask question here. I don't know I'm doing it in right way.

Upvotes: 3

Views: 317

Answers (1)

ggorlen
ggorlen

Reputation: 56945

I ran your tests. Here are my results on the three different datasets of size 30,000:

  dataset  |  time (s)  |   swaps
-----------+------------+----------
random     |  3.588447  | 221476595
descending |  2.588694  | 449985000
ascending  |  1.582666  |         0

What's going on here? Why is a randomized dataset slower than the "worst-case" descending dataset?

The answer seems to be branch prediction. The CPU makes a guess to see which branch will be taken in the code, executes it, and is correct 100% of the time in the descending dataset. This leads to significant performance increases and has been more elegantly explained before.

Having said that, the routine involves the same number of comparisons and time complexity is O(n2) in all cases.

Upvotes: 2

Related Questions