外壳排序和排序验证

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"; 
      } 
     } 
    } 

我不知道我在做什么错了，希尔排序实际上并没有对数组进行排序，或者至少它不会做降序排序，如果程序没有检查，以确保数组排序正确，它不会显示我希望显示的消息。

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

炮弹破裂。它似乎试图对间隙序列seq[]进行排序，当它应该排序值序列arr[]。另外，间隙序列应该是一系列值。例如：

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); 
} 

统称h在每次调用hsort的值是您的间隙序列。或者这些可以预先计算并存储。

---

测试为降序的顺序（或更精确地非升序）操作可以这样完成：

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; 
} 

然而，这种测试是不够的验证算法的正确性。考虑一个简单地将所有元素设置为单个值的函数。结果序列将通过这个测试。视觉检查 - 虽然在调试过程中有些用处，但容易出错并且不适合大型设备。

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