シェル並べ替えと並べ替えの確認

Question

私はかなり新しいコードを書いています。このコードでは、膨大な整数の配列をランダムに生成し、特定のシェルソートを選択して配列が正しくソートされました。私は私が間違ってやっているのか分からない

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

などのコードをコンパイルしてください。すべての警告をオンにして、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); 
} 

クヌースシーケンス：

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

しかし、この試験はアルゴリズムの正しさを検証するには不十分です。単純にすべての要素を単一の値に設定する関数を考えてみましょう。得られた配列はこの試験に合格する。ビジュアルインスペクションは、デバッグ中にやや役立ちますが、エラーが発生しやすく、大きなセットでは不可能です。

より良い解決策は、重複した配列を割り当てて、それを既知の良いアルゴリズムでソートし、各要素を同等かどうか比較することです。