Sorting Algorithm with C++

Homework – Sorting is fun

Record all the timings on the machines from the lab. Always check that you are the only person using that specific machine. You can look at the processes by using the commands top or htop. The only proces that uses more than 10 %CPU or 10 %MEM should be yours.

1. Investigate the execution time for sorting a vector (e.g. std::sort) for different op- timization options (try atleast -O0 and -O3). Sort an uniformly distributed vector of real values between 0 and r with r a chosen range variable (v[i] ∈ [0, r)). You can use the following commands assuming v is the vector of doubles

std::random_device rd;

std::mt19937 generator(rd());

std::uniform_real_distribution<> distribution(0, r);

for(auto& vi:v){

vi=distribution(generator);

}

Use the same framework as before with command line arguments for the size of the vector, the range, the number of experiments and the number of discarded timings. Shuffle the vector before each experiment. Create a graph of the execution time in function of the size of the vector for different compile options.

2. Implement bucket sort ([login to view URL]) which basically first places the elements in buckets, next each bucket is sorted and finally the sorted bucket elements are placed back in the original vector. Use an extra command line argument m for the number of buckets. Suppose the range r of the vector is 1000 and 10 buckets are used, the range for each bucket is 100. This means bucket 0 contains elements in [0, 100), bucket 1 [100, 200), ... and bucket 9 [900, 1000).

Hints:

• Interesting functions are std::ceil and std::floor

• Type conversion or type casting can be done by (type). This can be useful since

dividing two integers results in an integer value.

3. Compare your implementation of bucket sort with the standard sorting algorithm. What is the function of the number of buckets m. What are the advantages/disadvan- tages of both algorithms. Illustrate your explanation with (approximate) algorithmic complexities.

Thuật toán Lập trình C Lập trình C# Lập trình C++ Kiến trúc phần mềm

ID dự án: #15512726

Về dự án