Implementing a sort class using templates

Question

I posted last night about an array class, and now I'm having trouble with a sorting class. About half of the functions are defined, either by the professor or by the algorithms he gave us, but a lot of the definitions are confusing me. I'm not sure what makes them any different from the ones above it.

#ifndef SORTS_H
#define SORTS_H
#include <iostream>
#include <string>
#include "Array.h"
using namespace std;
template <class T>
void insertionSort(Array<T> &a);

template <class T>
void selectionSort(Array<T> &a);

template <class T>
void selectionSort(T a[], int n);

template <class T>
void mergesort(T *input, int size);

template <class T>
void mergesort(T *input, int left, int right, T *scratch);

template <class T>
T less(T x, T y);

template <class T>
void mergesort(Array<T> &input, int left, int right, Array<T>&scratch);

template <class T>
void mergesort(Array<T> & input);

Array<int> & random(int n);

template <class T>
void selectionSort(T a[], int n) {
    int i, j, tmp;
    int min_idx = 0;
    for (size_t i = 0; i < n-1; i++) {
        min_idx = i;
        for (size_t j = i+1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
            tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

template <class T>
void selectionSort(Array<T> &a) {
    int tmp;
    int min_idx = 0;

    for (int i = 0; i < a.getSize() - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < a.getSize(); j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
            tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

template <class T>
void insertionSort(Array<T> &a) {
    // put your code here 
}

template <class T>
bool sorted(Array<T> a) {

    for (int i = 1; i < a.getSize(); i++)
    if (a[i - 1] > a[i]) return false;

    return true;
}

Array<int> & random(int n) {
    Array<int> *tmp = new Array<int>(n);

    for (int i = 0; i < n; i++)
        (*tmp)[i] = rand() % 1000;

    return *tmp;
}

template <class T>
T less(T x, T y) {
    if (x < y) {
        return x;
    }
    else {
        return y;
    }
}

template <class T>
void mergesort(T *input, int left, int right, T *scratch) {
    if (right == left + 1) {
        return;
    }
    else {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length / 2;
        int l = left, r = left + midpoint_distance;

        mergesort(input, left, left + midpoint_distance, scratch);
        mergesort(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */
        for (i = 0; i < length; i++) {
            /* Check to see if any elements remain in the left array; if so,
            * we check if there are any elements left in the right array; if
            * so, we compare them.  Otherwise, we know that the merge must
            * use take the element from the left array */
            if (l < left + midpoint_distance &&
               (r == right || min(input[l], input[r]) == input[l])) {
                scratch[i] = input[l];
                l++;
            }
            else {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for (i = left; i < right; i++) {
            input[i] = scratch[i - left];
        }
    }
}

template <class T>
void mergesort(T *input, int size) {
    int *scratch = new int[size];
    mergesort(input, 0, size, scratch);
    delete [] scratch;
}

template <class T>
void mergesort(Array<T> &input, int left, int right, Array<T>&scratch) {
    if (right == left + 1) {
        return;
    }
    else {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length / 2;
        int l = left, r = left + midpoint_distance;

        mergesort(input, left, left + midpoint_distance, scratch);
        mergesort(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */
        for (i = 0; i < length; i++) {
            /* Check to see if any elements remain in the left array; if so,
            * we check if there are any elements left in the right array; if
            * so, we compare them.  Otherwise, we know that the merge must
            * use take the element from the left array */
            if (l < left + midpoint_distance &&
               (r == right || min(input[l], input[r]) == input[l])) {
                scratch[i] = input[l];
                l++;
            }
            else {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for (i = left; i < right; i++) {
            input[i] = scratch[i - left];
        }
    }
}

template <class T>
void mergesort(Array<T> &input) {
    // put your code here 
}

#endif

I also noticed that there is a void insertionSort(Array<T> &a); function, but the algorithm I was given is:

void insertionSort(int a[], int n){
    int tmp;
    int i, j;

    for (i = 1; i < n; i++) {
        tmp = a[i];

        for (j = i - 1; j >= 0; j--)

        if (a[j] > tmp) a[j + 1] = a[j];
        else break;
        a[j + 1] = tmp;
    }
}

Am I supposed to implement this the same way, just replacing int a[] with, say... &arr? I'm guessing since this includes array.h and the array class has T * arr;, I should be pointing to the address of that array? Would this also work for each definition that has the address operator in its parameter?

Answer 1

The difference is one, as you say, takes a typical int array a[], but how would you know the size? So this version requires the user to send it to the function with n as the number of elements. In your Array class you provide a size so there's no need for it. In general you're providing overloads for multiple situations.

I'm not sure what you mean by replacing int a[] w/ &arr, the signature is there, use what was given to you unless you're supposed to change it.

If you go back to your question about the Array class you can see an answer which uses the reference just as you would normally, i.e,

template <class T>
Array<T>::Array(const Array &other) : size(other.size), arr(new T[size])
{                        // ^^^^^^
  for (int i = 0; i < size; ++i)
    arr[i] = other.arr[i];
}         // ^^^^^

now apply it to this situation.

Also,

template <class T>
void selectionSort(Array<T> &a) {
    // I'm not sure I understand what this is supposed to do that's different from the above selectionSort.
    // I know that & is the reference operator, so should I just return whatever &a is?
}

You won't be returning anything here considering void as the return and the use of the reference. You pass by reference as opposed to by value so that what you do in the function is persistent. You could choose to pass back the sorted array and not use a reference but I'm fairly certain it'd be slower overall considering the assignment and copy. That's why the example from your other question is using const Array &other. It prevents the entire array, which may be large, from being copied and sent to the function as well as being changed.