How do I make a list that's length varies from 100 to 1000?

[Maddy Nay123]

I have been stuck on this for awhile. This code works on a online compiler but not Visual Studio and I have no idea how to do several things.
I don't know how to make a merge sort
I don't know how to make a list, let alone one that goes up to 1000
I don't know how to get the average of it being ran 10 times over (cause first after I run it the array becomes sorted already due to the prior sorts, which I also don't know how to resolve RIP)
I don't know how to have that write out to a csv file to be graphed

I have tried other sites, like StackOverflow, for help with the code but what they post doesn't make sense to me and/or doesn't work. Attached is my code that I have so far. Any help with all the issues I am having, especially with the list would be most apperciated. Sorry if I sound rude, I am really upset and frustrated with myself.

  /**Purpose of code: Create "list" class that represents a list of numbers of a given size
                    Create a function that is able to randomize your list of numbers
                    Implement the following methods to sort your List class:
                        - insertion sort (works with 8 values)
                        - merge sort (works with 6 values)
                        - quick sort (works with 6 values)
                        - median sort
                    Run each of these methods and record the run time of each at List lengths of:
                        - 100
                        - 200
                        - 300
                        - 400 
                        - 500
                        - 600
                        - 700
                        - 800
                        - 900
                        - 1000
                    Each of these 10 times and record the average of each run time
                        - write these out to a csv file
                    In excel (or similar tool) graph the average run time for each sorting method on the same plot to compare how each performs on each List size.
                    Repeat steps 3-4 when you attempt to sort an already-sorted list of numbers and record the findings
                    Repeat steps 3-4 when you attempt to sort a reverse-sorted list of numbers and record the findings
 **/
#include <iostream>
#include <stdio.h>
#include <list>
#include <chrono>
#include <algorithm>
using namespace std::chrono;
using namespace std;

// Part 2 to using Merge sort to sort my list
void merge(int arr[], int z, int l, int arr_size)
{
    int n1 = l - z + 1;
    int n2 = arr_size - l;
 
    int L[n1], R[n2];
 
    for (int i = 0; i < n1; i++)
        L[i] = arr[z + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[l + 1 + j];

    int i = 0;
    int j = 0;
    int k = z;
 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

//Function that uses Merge sort to sort my list
void mergeSort(int arr[], int z, int arr_size)
{
    int l;
        if(z < arr_size)
        {
            l = (z + arr_size)/ 2;
            mergeSort(arr, z, l);
            mergeSort(arr, z+1, arr_size);
            merge(arr, z, l, arr_size); //< not declared in scope?
        }
}

//Function to print out results of sorting using Merge sort method
void mergePrint(int arr[], int arr_size)
{
    int i; 
    cout << "Using Merge Sort method: ";
    for (i = 0; i < arr_size; i++)  
        cout << arr[i] << " "; 
}

//Part 3 to using Quick sort to sort my list
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
 
//Part 2 to using Quick sort to sort my list
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high]; // pivot 
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
 
    for (int j = low; j <= high - 1; j++) 
    { 
        // If current element is smaller than the pivot 
        if (arr[j] < pivot) 
        { 
            i++; // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

//Function that uses Quick sort to sort my list
void quickSort(int arr[], int low, int high)
{
    if (low < high) 
    { 
        int pi = partition(arr, low, high); 
 
        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
}

//Function to print out results of sorting using Quick sort method
void quickPrint(int arr[], int arr_size)
{
    int i; 
    cout << "Using Quick Sort method: ";
    for (i = 0; i < arr_size; i++)  
        cout << arr[i] << " ";  
}
/*
//Function that uses Median sort to sort my list
void medianSort()
{
    
}

//Function to print out results of sorting using Median sort method
void medianPrint()
{
    int i; 
    cout << "Using Median Sort method: ";
    for (i = 0; i < arr_size; i++)  
        cout << arr[i] << " ";  
}
*/
//Function that uses Insertion sort to sort my list
void insertionSort(int arr[], int arr_size)
{
    int i,j,k;  
        for (i = 1; i < arr_size; i++) 
        {  
            k = arr[i];  
            j = i - 1;  
                while (j >= 0 && arr[j] > k) 
                {  
                    arr[j + 1] = arr[j];  
                    j = j - 1;  
                }  
            arr[j + 1] = k;  
        }  
    }  
//Function to print out results of sorting using Insertion sort method
void insertionPrint(int arr[], int arr_size)  
{  
    int i; 
    cout << "Using Insertion Sort method: ";
    for (i = 0; i < arr_size; i++)  
        cout << arr[i] << " "; 

}

int main()
{
    // Declaring numbers
    int arr[] = {6, 10, 12, 3, 7, 1}; // tried with 8 values but Merge sort does not sort entirely
    int arr_size = sizeof(arr)/ sizeof(arr[0]);
    
    //Captures time it takes to run Merge Sort function
    auto mStart = high_resolution_clock::now();
    
        //Call Merge sort functions
        mergeSort(arr, 0, arr_size - 1);
        mergePrint(arr, arr_size);
    
    auto mStop = high_resolution_clock::now();
    auto mDuration = duration_cast<microseconds>(mStop - mStart);
    
    cout << "\nTime taken by Merge Sort function : "<< mDuration.count() << " microseconds" <<endl;
    
    
    //Captures time it takes to run Quick Sort function
    auto qStart = high_resolution_clock::now();
    
        //Call Quick sort functions
        quickSort(arr, 0, arr_size - 1);
        quickPrint(arr, arr_size);
    
    auto qStop = high_resolution_clock::now();
    auto qDuration = duration_cast<microseconds>(qStop - qStart);
    
    cout << "\nTime taken by Quick Sort function : "<< qDuration.count() << " microseconds" <<endl;
    
    //Captures time it takes to run Insertion Sort function
    auto iStart = high_resolution_clock::now();
    
        //Calls Insertion Sort functions
        insertionSort(arr, arr_size);
        insertionPrint(arr, arr_size);
    
    auto iStop = high_resolution_clock::now();
    auto iDuration = duration_cast<microseconds>(iStop - iStart);
    
   cout << "\nTime taken by Insertion Sort function : "<< iDuration.count() << " microseconds";
   
   
    return 0;
}

I get the code to do the sorting methods and time how long they take but that's about it. I want to have it so each sorting method is a seperate page so the code isn't so long. Please help me if you can! Thank you lots!!

[Rob Nelson]

C++ doesn't support dynamically sized arrays on the stack like C used to, and this is why it doesn't compile in MSVC.

You can use std::vector to get around that by not changing the source too much. There are more efficient ways to do it, but this works to get it going with minimal changes:

// int L[n1], R[n2];
std::vector<int> LL(n1);
std::vector<int> RR(n2);

int * L = &LL[0];
int * R = &RR[0];

So only those lines need to change and the source can be used as-is, at least until its known to work properly. Later, it can then refactored into something more efficient.

It will compile in MSVC with this change.


With the Merge Sort -- It looks like an assignment, so I don't want to do it, but I can give a couple pointers:

1. The merge sort doesn't work with 6 values and then not with 8 -- it was just a lucky set of numbers in the example. Try various other numbers and I don't think you'll get the same results as with the 6 numbers in the example (i.e. it doesn't work generally, which is a nicer clue about what is going wrong).

2. With the Merge function, think about how it looks at boundaries -- right edges and left edges of the array -- and how the size and starting point being passed in affect that as it becomes recursive.

Just some thoughts...