Week07 Lab Notes

Sorting Complexity Analysis

Preparation

Start your virtual machine, password : CompSys2025!

Download week07.zip from Blackboard ( in labs of Week 7)

Store or move week07.zip to the lab folder on the desktop

Start Cygwin and cd the lab folder

Unzip week07.zip

You can use Windows Explorer to unzip week07.zip or simply run the following command in Cygwin

unzip week07.zip

Build the project

Go to src folder and build the the project with the make command

make

It will generate two excecutables : bubblesort and mergesort.

Both bubblesort and mergesort take an array length parameter as their paramters, such as

bubblesort 1000

If no array length is input, the default array length for is 10000 for bubble sort and 100,000 for merge sort.

We can use the time command to measure the running time of a program, such as

time ./bubblesort 20000

Real is the actual elapsed time

User is the amount of CPU time spent in user-mode code (outside the kernel) within the process. and sys is the time spent one system calls.

Sys is the amount of CPU time spent in the kernel within the process.

In the following, we will examine the time needed for bubble sort and merge sort with different array size.

Expriements

Bubble sort

Bubblesort comes with an average time complexity of $O(n^2)$

Run bubblesort with following 2 configurations:

time ./bubblesort 10000
time ./bubblesort 100000

The number specifies the length of the int array.

The following is what I got on my VM:

Check if the ratio of runtime roughly matches the time complexity.

Eastimate time needed for bubblesort 1000000

Test bubblesort with other array lengths.

Merge sort

Mergesort comes with a time complexity of $O(n \log n)$

Run mergesort with following 2 configurations:

time ./mergesort 100000
time ./mergesort 1000000
time ./mergesort 10000000

The following is what I got on my VM:

Check if the ratio of the rumtime roughly matches the time complexity.

Compare the time of bubblesort and mergesort for the 100,000 array length. Try to explain why mergesort is over 2000 times faster than bubble sort from the perspective of their corresponding time complexity.

Eastimate time needed for mergesort 100,000,000

run

time ./mergesort 100000000

to see if it roughly matches your estimation

Test mergesort with other array lengths.