Sorting a non-copy array

Question

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.

Manually copy the elements with a loop to three separate arrays ... Also, if you prof is actively telling you not to use the STL, then they are a terrible prof (exception being for learning purposes, but `std::copy` is hardly something to worry about). — ChrisMM, May 20 '23 at 19:07
A couple of things related to your code, but not necessarily to your problem: Call `srand` *once* only in your program, preferably among the first things in your `main` function. But also don't use `srand` and `rand`, C++ have [much better PRNG facilities](https://en.cppreference.com/w/cpp/numeric/random). Then don't allocate memory yourself. Use either `std::vector` if you need a truly dynamic array, or `std::array` if you don't. — Some programmer dude, May 20 '23 at 19:09
Your prof may have reasons to avoid STL-ish parts from the C++ ISO Standard, but that's a questionable advise for general C++, as is use of vector new and manual resource management in general. That said, concerning your problem, please extract a [mcve] from your code and include that in your question. As a new user here, please also take the [tour] and read [ask]. — Ulrich Eckhardt, May 20 '23 at 19:10
@Someprogrammerdude I'd love to but I can't use the STL containers unfortunatley — underloaded_operator, May 20 '23 at 19:10
Also, why sort the array multiple times? What difference would that make between the sorting calls? You never shuffle the array (as far as we can see) so once sorted it should hopefully stay sorted no matter how many times you call different sorting functions. — Some programmer dude, May 20 '23 at 19:11
I forgot to add the "instructions" to my question. The purpose of the lab is to make a working implementation of QS, MS an HS and print the results in main. I figured having the same array would show best that the algorithm works since the user could compare results and see that the output is the same — underloaded_operator, May 20 '23 at 19:14
For that you should create three new copies of the original array with the random values. Then pass each array-copy to each of the sorting functions. Then compare the three arrays to make sure they are all the same. So you should have a total of four arrays: The original unsorted array, and one each for each sorting function. — Some programmer dude, May 20 '23 at 19:21
@Dude [How to implement sorting algorithms using modern C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, May 20 '23 at 20:58

score 3 · Accepted Answer · answered May 20 '23 at 19:09

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.

score 1 · Answer 2 · edited May 20 '23 at 19:29

You could manually copy your array like this:

for (int i = 0; i < size; i++) {
    destination[i] = src[i];
}

Or you could use memcpy. Example from the link:

/* memcpy example */
#include <stdio.h>
#include <string.h>

struct {
  char name[40];
  int age;
} person, person_copy;

int main ()
{
  char myname[] = "Pierre de Fermat";

  /* using memcpy to copy string: */
  memcpy ( person.name, myname, strlen(myname)+1 );
  person.age = 46;

  /* using memcpy to copy structure: */
  memcpy ( &person_copy, &person, sizeof(person) );

  printf ("person_copy: %s, %d \n", person_copy.name, person_copy.age );

  return 0;
}

and, of course you can use std::copy as well, even though it's not an option due to the preferences of your professor.

Nitpick: as this is C++ (sans STL) I would suggest including `` and ``. — Chris, May 20 '23 at 19:23

Sorting a non-copy array

2 Answers2