### How do I make a list that's length varies from 100 to 1000? 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.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234`` `````` /**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 #include #include #include #include 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); //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(mStop - mStart); cout << "\nTime taken by Merge Sort function : "<< mDuration.count() << " microseconds" <(qStop - qStart); cout << "\nTime taken by Quick Sort function : "<< qDuration.count() << " 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!!
Last edited on 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;
int * R = &RR;

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...

Last edited on