外殼排序和排序驗證

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

然而，這種測試是不夠的驗證算法的正確性。考慮一個簡單地將所有元素設置爲單個值的函數。結果序列將通過這個測試。視覺檢查 - 雖然在調試過程中有些用處，但容易出錯並且不適合大型設備。

一個更好的解決方案是分配一個重複數組，並用已知的好算法對其進行排序，然後比較每個元素的相等性。