I am working on my lab #5 and it’s about sorting algorithms such as Quick Sort, Heap Sort and Merge Sort. I am somewhat done besides measuring the execution time and some other stuff, and I ran into an issue.

in this code:

  int *arr = fill();
  int size = 10;

  std::cout << "\nMERGE SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  merge_sort(arr,size);
  std::cout << "array#2: ";
  print_arr(arr,size);

  std::cout << "\nQUICK SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  quick_sort(arr, size);

  std::cout << "array#2: ";
  print_arr(arr, size);

  std::cout << "\nHEAP SORT: \n";
  std::cout << "array#1: ";
  print_arr(arr, size);

  heap_sort(arr, size);

  std::cout << "array#2: ";
  print_arr(arr, size);

  delete[] arr;

I am passing my array to all of the sorting methods and what’s happening is that the array get’s sorted with Merge Sort, which works fine but then that sorted array is being passed into Quick Sort and Heap Sort.

I did some research and I found that I can use std::copy() to create copies of the array and them pass them separatley as copies, but I know my professor is not a "fan" of the STL and usually tells us to not use it if it’s not our last resort.

My restrictions for this assigment are some prototypes such as this function:

const int MAX = 100000;
int* fill() {
    int* arr = new int[10]; // create a new array of size 100

    // set the seed for the random number generator
    std::srand(static_cast<unsigned int>(std::time(nullptr)));

    for (int i = 0; i < 10; i++) { //!change to MAX
        arr[i] = std::rand() % 10 + 1; // fill the array with random numbers from 1 to 100
    }
    return arr;
}

and

void heap_sort(int *arr, int size);
void merge_sort(int *arr, int size)
void qucik_sort(int *arr, int size)

So far all the algorithms work since I tested them separatley, but when I run them all together it sorts the already sorted array. This affects the QS algorithm.

I know it looks like spaghetti code right now, function pointers are on the TODO list.

>Solution :

You need to generate the array and then copy it. You might do something like:

int* copy_array(int* arr, std::size_t n) {
    int* new_arr = new int[size];

    for (std::size_t i = 0; i < n; i++) {
        new_arr[i] = arr[i];
    }

    return new_arr;
}

Then simply call this to create as many copies of your array as you need before sorting it.