Shell排序和排序验证

Question

我是一个编程新手，我一直在努力使用这段代码，它将允许我随机生成大量整数数组，选择特定的shell排序，然后测试该数组是否正确排序。

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define LISTLEN 100000
using namespace std;

void shellSort(int[], int, int[], int);
void testIfSorted(int[], int);

void main()
{
   {
    int list[LISTLEN];
    int seq1[] = {LISTLEN/2};
    int seq2[] = {2-1};
    int seq3[] = { 4 + 3 * (2 ^ 0) + 1 };
    int choice;

    for (int i = 1; i < LISTLEN; i++)
    {
        list[i] = rand() % LISTLEN + 1;

        cout << list[i] << endl;
    }
    cout << "\nEnter the Number for Which Sequence-Type You Wish to Use: \n"
        "1) Shell Sequence\n"
        "2) Hibbard Sequence\n"
        "3) Sedgewick Sequence\n";
        cin >> choice;

        if (choice == 1)
        {
            shellSort(list, LISTLEN, seq1, LISTLEN / 2);
        }
        else if (choice == 2)
        {
            shellSort(list, LISTLEN, seq2, (2 - 1));
        }
        else if (choice == 3)
        {
            shellSort(list, LISTLEN, seq3, (4 + 3 * (2 ^ 0) + 1));
        }

        cout << "\nVerifying List was Sorted\n";
            testIfSorted;
    }
}

    void shellSort(int arr[], int arrsize, int seq[], int seqsize)
    {
        clock_t t;
        t = clock();
        {
            int j, temp;
            for (int i = seqsize; i < arrsize; i += 1)
            {
                temp = seq[i];
                for (j = i; j >= seqsize && seq[j - seqsize] > temp; j -= seqsize)
                {
                    seq[j] = seq[j - seqsize];
                }
                seq[j] = temp;
                cout << temp << endl << endl;
            }
            t = clock() - t; 
            printf("It took me %d clicks (%f seconds).\n", t, ((float)t) / CLOCKS_PER_SEC);
        }
    }

    void testIfSorted(int list[], int length)
    {
        for (int i = 0; i < length - 1; i++)
        {
            if (list[i] < list[i + 1])
            {
                cout << "List Isn't Sorted Correctly\n";
            }
            else (list[i] > list[i + 1]);
            {
                cout << "List Sorted Correctly\n";
            }
        }
    }

我不知道我做错了什么，shell排序实际上不会对数组进行排序，或者至少它不会进行降序排序，如果程序确实检查了数组是否正确排序，它就不会显示我希望显示的消息。

Answer 1

我没有具体的答案，但以下是一些快速调试技巧：

1-通过clang-format运行代码。如果您不能/不能在您的计算机上安装它，可以使用在线格式化程序，如http://format.krzaq.cc/

2-使用clang编译器编译代码，并打开所有警告。同样，如果你不能/不能在你的电脑上安装clang，有一些在线沙箱可以玩。为什么是Clang？他们做了很大的努力来给它提供非常漂亮的警告/错误消息。

我两个都做了，这就是clang对这个程序的看法(链接here)

prog.cc:10:1: error: 'main' must return 'int'
void main()
^~~~
int

prog.cc:41:9: warning: expression result unused [-Wunused-value]
        testIfSorted;
        ^~~~~~~~~~~~

prog.cc:61:56: warning: format specifies type 'int' but the argument has type 'clock_t' (aka 'long') [-Wformat]
        printf("It took me %d clicks (%f seconds).\n", t, ((float)t) / CLOCKS_PER_SEC);
                           ~~                          ^
                           %ld

prog.cc:45:20: warning: unused parameter 'arr' [-Wunused-parameter]
void shellSort(int arr[], int arrsize, int seq[], int seqsize)
                   ^

prog.cc:72:22: warning: expression result unused [-Wunused-value]
            (list[i] > list[i + 1]);
             ~~~~~~~ ^ ~~~~~~~~~~~

4 warnings and 1 error generated.

这些可能会有帮助--特别是最后一个！

Answer 2

脱壳装置坏了。当它应该对值序列arr[]进行排序时，它似乎正在尝试对间隙序列seq[]进行排序。此外，间隔序列应该是一系列值。例如：

static void hsort(int a[], size_t n, size_t h)
{
    for ( size_t i, j = h; j < n; j++ ) {
        int temp = a[j];
        // @note the comparison is setup for descending.
        for ( i = j; i >= h && temp > a[i-h]; i -= h )
            a[i] = a[i-h];
        a[i] = temp;
    }
}

外壳序列：

void shellsort1(int a[], size_t n)
{
    for ( size_t h = n/2; h > 0; h /= 2 )
        hsort(a, n, h);
}

Knuth序列：

void shellsort2(int a[], size_t n)
{
    size_t i, h = 0;
    while ( 2*(i = h*3+1) <= n )
        h = i;
    for ( ; h > 0; h /= 3 )
        hsort(a, n, h);
}

总而言之，每次调用hsort时h的值就是您的间隙序列。或者，这些也可以预先计算并存储。

测试序列的降序(或者更准确地说，非升序)可以使用以下命令完成：

bool is_descending(int a[], size_t n)
{
    for ( size_t i = 1; i < n; i++ )
        if (a[i-1] < a[i])
            return false;
    return true;
}

然而，这种测试不足以验证算法的正确性。考虑一个简单地将所有元素设置为单个值的函数。生成的序列将通过此测试。目视检查-虽然在调试期间有点有用-很容易出错，而且对于大型集合是不可能的。

一种更好的解决方案是分配一个重复的数组，并使用已知的良好算法对其进行排序，然后比较每个元素是否相等。