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?

These are method overloadings. So different method with same name achieves the same goal with different number and/or type of parameters. — Fallen
– Fallen, Commented Nov 18, 2013 at 21:09
Unrelated: Shal can assume std::merge or std::inplace_merge, std::partition, std::upper_bound, and std::rotate are all off the table? Because utilizing those without actually using the standard library sorting algorithms could reduce the footprint of this by about 80+%. — WhozCraig
– WhozCraig, Commented Nov 18, 2013 at 21:21

ChiefTwoPencils · Accepted Answer · 2013-11-18 22:35:52Z

2

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.

edited Nov 18, 2013 at 22:35

answered Nov 18, 2013 at 21:33

ChiefTwoPencils

14k8 gold badges55 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

iKyriaki Over a year ago

So, using the example from my Array class, would the code for void selectionSort(Array<T> &a); be similar, just with a.whatever?

ChiefTwoPencils Over a year ago

Well that depends. You can do a.whatever if whatever is public. If it's private you'd need to implement getters/setters.

ChiefTwoPencils Over a year ago

@iKyriaki: the example is actually a little funny, IMHO, you have the [] operator overloaded so other.arr[i] should result in the same thing as other[i], unless I'm missing something by skimming.

iKyriaki Over a year ago

I'm honestly not too sure. I'm still very fuzzy on operator overloads and mostly used previous examples of code in my attempt to complete the Array class.

iKyriaki Over a year ago

I added in my code attempt for the void selectionSort(Array<T> &a). Using your suggestion, I managed to make changes (although not many), but now I keep getting the warning that i and j are unreferenced local variables.

|

Collectives™ on Stack Overflow

Implementing a sort class using templates

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related