3

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.

Jiseong
  • 89
  • 6
  • Where have you looked? Wikipedia on [Bubble Sort](https://en.wikipedia.org/wiki/Bubble_sort) vs [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort) vs [Selection Sort](https://en.wikipedia.org/wiki/Selection_sort) — I happen to be using those pages at the moment, so I have the tabs open. – Jonathan Leffler Nov 24 '18 at 07:20
  • How reliable are those times? You presumably ran them multiple times and got stable results. You should check that the `fread()` call returns `30000`. (I'd add two pairs of braces to your code, one for each `for` loop, too.) – Jonathan Leffler Nov 24 '18 at 07:23
  • @JonathanLeffler Oh I've just added those braces. And I don't catch your saying about `fread()`. – Jiseong Nov 24 '18 at 09:34
  • In general, you need to check that if you expect to read 30,000 integers, `fread()` reports that it was actually able to read 30,000 integers and not some smaller number of integers. – Jonathan Leffler Nov 24 '18 at 09:39
  • Oh I got it. I didn't know well about return of `fread()`. I've just checked it through gdb. – Jiseong Nov 24 '18 at 09:50

1 Answers1

2

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.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
  • Wow. I had difficulty understanding it through first link, but I've understood it through the second link. Actually this issue seems to be beyond the scope of my class, (we have to compile with optimization level -O0.) but very meaningful to me. Thank you. – Jiseong Nov 24 '18 at 09:44
  • @Jiseong: You have to compile with `-O0` (no optimization, using GCC)? That's weird. Well, you should also compile with more options — I recommend `gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes …` and don't run the program until it compiles cleanly (in fact, the `-Werror` means you won't be able to run the program until it compiles cleanly). Then, if necessary, you can drop the optimization back to `-O0` to satisfy the rather peculiar requirements of the course, but some of the problems that are identified with the `-O3` level won't be reported at `-O0`. – Jonathan Leffler Nov 24 '18 at 10:09
  • @JonathanLeffler Thank you for recommend that option. It will be helpful for me to do another coding.But what I mean with "have to compile with -O0" is that, `Makefile` and directory structure of source file and header file is just given by TA. I cannot wholly understand lecturer's intention, but it's just assignment. – Jiseong Nov 24 '18 at 14:53
  • You can edit the makefile while you’re working on the task to be more stringent. When you’re about to submit, use the official copy instead. Apart from your program running slowly (because it is unoptimized), there should be no problem. – Jonathan Leffler Nov 24 '18 at 14:57