Description

The purpose of this challenge is to compare two different sorting algorithms.

Requirements

1. Write a function void fill_array_random(int array[], int size, int lbounds, int ubounds). This function will fill an array of size with values that are between lbounds and ubounds. 

   int num = (rand() % (ubounds - lbounds)) + lbounds;
   

2. Write a function void fill_array_inc(int array[], int size). This function will fill the array with each element containing increasing values, starting from 1 to size.
3. Write a function void fill_array_dec(int array[], int size). This function will fill the array with each element containing decreasing values, starting from size to 1.
4. Write a function void bubble_sort(int array[], int size). This function will sort array using the bubble sort algorithm.
5. Write a function void insertion_sort(int array[], int size). This function will sort array using the insertion sort algorithm.
6. You could also write a show_array(int array[], int size) function. Then, you could call this function using small values of size to prove that your bubble_sort() and insertion_sort() functions are working correctly.
7. In main(), ask the user for the sample data size, and create an int array of this size.
8. Use the code sequence below, or something similar, to test sort times using the bubble sort algorithm. Assuming you wrote the show_array() function, you can also call show_array() to ensure that your sorting algorithms work, before you add any timing code.

   #include <chrono>
   #include <cstdlib>
   #include <ctime>
   
   ...
   
   int main()
   {
     srand(time(NULL));
     // more code here
     
     cout << "Bubble sort (Random) took ";
     fill_array_random(array, arraysize, 1000, 1000000);
   
     auto start = chrono::steady_clock::now();
     bubble_sort(array, arraysize);
     auto end = chrono::steady_clock::now();
     cout << chrono::duration_cast<chrono::milliseconds>(end-start).count() << endl;
   
     cout << "Bubble sort (Increasing) took ";
     fill_array_inc(array, arraysize);
   
     start = chrono::steady_clock::now();
     bubble_sort(array, arraysize);
     end = chrono::steady_clock::now();
     cout << chrono::duration_cast<chrono::milliseconds>(end-start).count() << endl;
   
     cout << "Bubble sort (Decreasing) took ";
     fill_array_dec(array, arraysize);
   
     start = chrono::steady_clock::now();
     bubble_sort(array, arraysize);
     end = chrono::steady_clock::now();
     cout << chrono::duration_cast<chrono::milliseconds>(end-start).count() << endl;
   
   }

9. Duplicate the code above for testing out the insertion sort algorithm. Similarly, fill the array out the three different ways – random, increasing, decreasing. Then call the insertion_sort() function using the timing sequence as above.
10. Run the program with different array sizes (100, 1000, 1000000, etc) to get a more accurate depiction of the difference in timings.