insertion sort, heap sort , merge sort, quick sort together. can you find me the solution why cant i run the program?

  //Hey there i m facing some serious problem to run the following code,      
    // please help!! 

1. Implement the INSERTION-SORT, MERGE-SORT, HEAP-SORT, and QUICK-SORT algorithms in such a way so that they can sort a given list of pairs of numbers into increasing order. To illustrate, suppose the input list contains: (4,3), (4,4), (3,3), (3,4). Then the output of your sorting algorithm will be: (3,3), (3,4), (4,3), (4,4), i.e., (x1,y1) <= (x2,y2) if – (a) x1 <= x2 or (b) x1 == x2 but y1 <= y2 Write a single program in such a way that the user can choose which sorting-algorithm s/he wants to use on the input. Implement your code in C++/Java. Upload this code in Engrade.

Hint: Ask the user to provide a list of pairs of numbers in a file called “input.txt” where each line contains one number. For e.g., “input.txt” may contain: 3 3 4 3 3 4 4 4 Your code will read this file and will output a similar file called “output.txt” where the given numbers will be printed in sorted order; for e.g., for the above input, “output.txt” will contain: 3 3 3 4 4 3 4 4

2. Analyze the worst case running times of the above mentioned four algorithms. Explain how you derived this worst case running time using detailed calculation as done in the book. Write this down by hand and submit it in the class.

3. Use random.org's integer number generator (URL: https://www.random.org/integers/) to generate four lists of integers with 10, 100, 1000, and 10K pairs of integers. Sort these four lists using each sorting-algorithm you wrote in question 1 and note the time taken by each program for each input list. Plot the times for each sorting program in Y-axis and the corresponding input sizes (number of integer-pairs in the list) in the X-axis. Show a single plot by which we can compare the performance of the four sorting algorithms. Comment on this plot e.g. which sorting program is the fastest, why do you think it runs faster than others (is it because of implementation, or it is the characteristic of that algorithm?), etc. Print the plots and explanation/comment and submit this in the class along with your hand-written answer to question#2 as well as the code for question#1<<

   #include #include #include

   using std::cout; using std::endl;

   #define PARENT(i) ((i - 1) / 2) #define LEFT(i) (2 * i + 1) #define RIGHT(i) (2 * i + 2

   void insertion_sort(int list[], int size) { for(int j=1;j-1 and list[i]>key) { list[i+1]=list[i]; i=i-1; } list[i+1]=key;

   } }

   1. [

List item

]1

=========

//end of insertion sort

     void merge(int list[], int p, int q, int r)
       {

        int n1=q-p+1;
        int n2=r-q;
        int L[n1+1];
    int R[n2+1];
  for(int i=0;i<n1; i++)
   {
      L[i]=list[p+i];
      }
        for(int j=0;j<n2; j++)
            {
       R[j]=list[q+1+j];
         }


   int largest;
      if(L[n1-1]<R[n2-1]) largest=R[n2-1]; else largest=L[n1-1];
       L[n1]=largest+1;
      R[n2]=largest+1;

     int i=0;
       int j=0;
         for(int k=p; k<=r; k++)
      {
      if (L[i]<=R[j])
        {
      list[k]=L[i];
              i++;
     } else
    {
     list[k]=R[j];
     j++;
   }
     }
   }

     void merge_sort_aux(int list[], int p, int r)  //another function
       {
       if(p<r)
         {
        int q=floor((p+r)/2);
       merge_sort_aux(list,p,q);
         merge_sort_aux(list,q+1,r);
           merge(list,p,q,r);
   }



    }

    void merge_sort(int list[], int size)
     {
   merge_sort_aux(list, 0, size - 1);
    }



       class heap
        {
        public:
        int *nodes;
        int length;
        int heap_size;
      };



        void max_heapify(heap list, int index)
      {

    int left,right,largest,exchange_temp;

    left = LEFT(index);
    right = RIGHT(index);

    if(left <list.heap_size && list.nodes[left] > list.nodes[index])
    {
        largest = left;
    } else
    {
        largest = index;
    }

    if(right <list.heap_size && list.nodes[right] > list.nodes[largest])
    {
        largest = right;
    }


    if(largest != index)
    {
        exchange_temp = list.nodes[index];
        list.nodes[index] = list.nodes[largest];
        list.nodes[largest] = exchange_temp;
        max_heapify(list, largest);
    }

   }



        void build_max_heap(heap list)
    {
     list.heap_size = list.length;
          for(int i = floor(list.length/2); i>=0; i--)
          {
               max_heapify(list, i);
             }
          }



      void heap_sort(int list[], int size)
  {
int exchange_temp;
heap tempheap;
tempheap.length = size;
tempheap.nodes = list;
tempheap.heap_size = size;
build_max_heap(tempheap);


for(int i= tempheap.length - 1; i>=1; i--)
{
    exchange_temp = tempheap.nodes[0];
    tempheap.nodes[0] = tempheap.nodes[i];
    tempheap.nodes[i] = exchange_temp;
    tempheap.heap_size = tempheap.heap_size - 1;

    max_heapify(tempheap,0);
       }

       }


       int partition(int list[], int p, int r)
      {
int pivot, index, exchange_temp;
pivot = list[r];
index = p - 1;
for(int i = p; i < r; i++)
{
    if(list[i] <= pivot)
    {
        index++;
        exchange_temp = list[i];
        list[i] = list[index];
        list[index] = exchange_temp;
    }
}
exchange_temp = list[r];
list[r] = list[index+1];
list[index+1] = exchange_temp;
return index+1;
   }

 void quicksort_aux(int list[], int p, int r)
  {
      int q;
    if(p<r)
       {
         q = partition(list, p, r);
          quicksort_aux(list, p, q-1);
          quicksort_aux(list, q+1, r);
        }
     }

     void quick_sort(int list[], int size)
    {
       quicksort_aux(list,0, size-1);
          }



      int main()
    { 

            std::chrono::high_resolution_clock::time_point t1,t2;
          srand(time(0));

     int npointsmax = 100000, nave = 100, npoints = 46;
    double  bubble_timelist[npoints],                                                 insertion_timelist[npoints],merge_timelist[npoints], quick_timelist[npoints],                                    heap_timelist[npoints];

          int *rlist1= new int[npointsmax];
  int *rlist2= new int[npointsmax];
  int *rlist3= new int[npointsmax];
  int *rlist4= new int[npointsmax];
  int *rlist5= new int[npointsmax];



  double nplist[npoints];
  nplist[0] = 1;
 for(int n=0;n<5;n++)
{
    for(int j=2;j<11;j++)
    {
        nplist[9*n + j - 1] = j * pow(10,n);
    }
}

  int icounter = 0;

  cout<<"Number of random points being sorted:n";

for (int npointsi : nplist)

{

    double ins_temp_timer = 0.0;
    double hp_temp_timer = 0.0;
    double mg_temp_timer = 0.0;
    double qk_temp_timer = 0.0;
    cout<<npointsi<<endl;
    for(int j = 0; j< nave; j++)
    {


        for(int ii=0;ii<npointsi;ii++)
        {
            rlist1[ii]=rlist2[ii]=rlist3[ii]=rlist4[ii]=rlist5[ii]=rand() % 1000;
        }



        t1 = std::chrono::high_resolution_clock::now();
        merge_sort(rlist1,npointsi);
        t2 = std::chrono::high_resolution_clock::now();
        mgtime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
        mg_temp_timer += mgtime ;

        t1 = std::chrono::high_resolution_clock::now();
        heap_sort(rlist2,npointsi);
        t2 = std::chrono::high_resolution_clock::now();
        hptime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
        hp_temp_timer += hptime ;

        t1 = std::chrono::high_resolution_clock::now();
        quick_sort(rlist3,npointsi);
        t2 = std::chrono::high_resolution_clock::now();
        qktime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
        qk_temp_timer += qktime ;


        if(npointsi<=500)
        {
            t1 = std::chrono::high_resolution_clock::now();
            bubble_sort(rlist4,npointsi);
            t2 = std::chrono::high_resolution_clock::now();
            bbtime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
            bb_temp_timer += bbtime ;

            t1 = std::chrono::high_resolution_clock::now();
            insertion_sort(rlist5,npointsi);
            t2 = std::chrono::high_resolution_clock::now();
            instime = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();
            ins_temp_timer += instime   ;
        } else
        {
            bb_temp_timer = 0.0;
            ins_temp_timer = 0.0;
        }

    }


    merge_timelist[icounter] = mg_temp_timer/nave;
    heap_timelist[icounter] = hp_temp_timer/nave;
    quick_timelist[icounter] = qk_temp_timer/nave;
    insertion_timelist[icounter] = ins_temp_timer/nave;

    icounter++;

}



FILE * resultsfile;
resultsfile=fopen("results-comparison_sort-noBS.dat","w");
for(int j=0;j< npoints;j++) fprintf(resultsfile, "%5e t %10.2f t %10.2f t %10.2f t %10.2f t %10.2f n",nplist[j], bubble_timelist[j], insertion_timelist[j], merge_timelist[j], heap_timelist[j], quick_timelist[j]);
fclose(resultsfile);

}