In this team-based homework, you’ll use any resources available to create the fa

Q: In this team-based homework, you’ll use any resources available to create the fa

int partition(int* A, int low, int high){ int pivot = A[high]; int i = (low-1); int temp; for (int j = low; j

ID: 3708930 • Letter: I

Question

In this team-based homework, you’ll use any resources available to create the fastest sorting algorithm possible. Bonus points will go to the fastest algorithms!

The following files have been given to you:

1. A C++ header file (sort.h) declaring a sort function.

2. A C++ source file (main.cpp) containing a main function with tests.

The sorting algorithm in your submission can be based on any combination of sorting algorithms, but must contain references (as comments in sort.cpp) to algorithm resources used. Feel free to implement helper functions in sort.cpp

Here are some suggestions:

• Focus on algorithms, not line-by-line optimization.

• Don’t sort if you don’t have to, i.e. if the array is already sorted.

• The “best” algorithm varies based on input; it may be worth first looking at the input (quickly) and picking an algorithm based on the contents.

• Use online resources to see what algorithms are out there and what inputs they are good for. Many well-known algorithms, e.g. quick sort, have several variations

//MAIN.CPP

#include <algorithm>
#include <iostream>
#include <chrono>
#include <cstdlib>
#include "sort.h"

using namespace std;
using namespace chrono;

inline void _test(const char* expression, const char* file, int line)
{
   cerr << "test(" << expression << ") failed in file " << file;
   cerr << ", line " << line << "." << endl;
        abort();
}

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))

// A basic sorting algorithm (merge sort) to compare
// against your sorting algorithm for correctness and speed.
void benchmark_sort(int* A, int n)
{
   if (n < 2)
       return;
   int halfway = n/2;
   benchmark_sort(A, halfway);
   benchmark_sort(&(A[n/2]), n - halfway);
   int i, j, copied_elements;
   i = 0;
   j = halfway;
   copied_elements = 0;
   int* sorted_A = new int[n];
   while (copied_elements < n)
   {
                if (j == n)
                {
                        sorted_A[copied_elements] = A[i];
                        ++i;
                }
       else if (i == halfway)
       {
           sorted_A[copied_elements] = A[j];
           ++j;
       }
       else if (A[i] < A[j])
       {
           sorted_A[copied_elements] = A[i];
           ++i;
       }
       else
       {
           sorted_A[copied_elements] = A[j];
           ++j;
       }
       ++copied_elements;
   }
   for (int i = 0; i < n; ++i)
       A[i] = sorted_A[i];
   delete[] sorted_A;
}

int main()
{
   srand(2017); // Initializes random number generation
   system_clock::time_point start, end;
   float dur;

   // Variables used later
   const int n = 5000000;
   int* A = new int[n];
   int* B = new int[n];
   float total_duration = 0;
   float total_benchmark_duration = 0;

   // Test 1: already in sorted order
   for (int i = 0; i < n; ++i)
       A[i] = B[i] = i+1;

   start = system_clock::now();
   sort(A, n);
   end = system_clock::now();
   dur = duration<float>(end - start).count();
   total_duration += dur;
   cout << "Test #1 time: " << dur << " seconds." << endl;