使用模板实现排序类

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(Array &a);函数,但我给出的算法是:

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?

我是否应该以同样的方式实现这一点,只需用一个[]代替int,比如说...&arr?我猜测,因为这包括array.h并且数组类有T * arr;,我应该指向该数组的地址?这也适用于在其参数中具有地址运算符的每个定义吗?

1 个解决方案

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

正如你所说,差异是一个典型的int数组a [],但你怎么知道它的大小?因此,此版本要求用户将其作为元素数量发送到函数。在您的Array类中,您提供了一个大小,因此不需要它。通常,您会为多种情况提供重载。

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.

我不确定你的意思是替换int [] w /&arr,签名就在那里,使用给你的东西,除非你应该改变它。

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,

如果你回到你关于Array类的问题,你可以看到一个答案,正如你通常那样使用引用,即,

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.

考虑到无效作为返回和使用参考,您将不会返回任何内容。您通过引用传递而不是按值传递,以便您在函数中执行的操作是持久的。您可以选择传回已排序的数组而不使用引用,但我相当确定它在整体考虑分配和复制时会更慢。这就是为什么你的另一个问题的例子是使用const Array&other。它可以防止整个数组(可能很大)被复制并发送到函数以及被更改。

#1