Shell Sortierung und Sortierung Verifikation

Question

Ich bin ziemlich neu im Codieren und ich habe mit diesem Code gekämpft, der es mir erlaubt, zufällig ein riesiges Array von Ganzzahlen zu erzeugen, eine bestimmte Shell-Sortierung auszuwählen und dann zu testen, ob das Array war richtig sortiert.

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

Ich weiß nicht, was ich falsch mache, wird der Shellsort nicht tatsächlich das Array sortieren oder zumindest nicht eine absteigende Sortierung tun, und wenn das Programm nicht überprüft, um sicherzustellen, Das Array ist korrekt sortiert und zeigt nicht die Nachricht an, die angezeigt werden soll.

Answer 1

Ich habe keine bestimmte Antwort, aber diese sind ein paar schnelle Tipps zur Fehlerbehebung:

1 - den Code durch clang-format laufen. Wenn Sie nicht/kann sie nicht auf Ihrem Computer installiert haben, gibt es Online-Formatierer zur Verfügung wie http://format.krzaq.cc/

2 - kompilieren Sie Ihren Code mit dem clang Compiler mit allen Warnungen eingeschaltet. Auch wenn Sie clang nicht auf Ihrem Computer installieren können/können, gibt es ein paar Online-Sandboxen, mit denen Sie spielen können. Warum Clang? Sie haben sich große Mühe gegeben, sehr schöne Warn-/Fehlermeldungen zu geben.

Ich habe beide, und das ist, was clang über das Programm (Link 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. 

Diese helfen könnte zu sagen hatte - vor allem die letzte!

Answer 2

Der Shellsort ist defekt. Es scheint die Lücke Sequenz seq[] zu sortieren versucht zu werden, wenn es die Wert Sequenz arr[] Sortierung werden soll. Zusätzlich sollte die Lückensequenz eine Reihe von Werten sein. Zum Beispiel:

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

Shell-Sequenz:

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

Knuth Reihenfolge:

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

Zusammengefasst werden die Werte von h bei jedem Aufruf hsort ist Ihre Lücke Sequenz. Alternativ können diese vorberechnet und gespeichert werden.

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

jedoch dieser Test nicht ausreicht Richtigkeit für die Überprüfung Algorithmus:

---

für den Abstieg der Sequenz Testen (oder genauer gesagt nicht-aufsteigend) verzichtet werden kann. Betrachten Sie eine Funktion, die einfach alle Elemente auf einen einzelnen Wert setzt. Die resultierende Sequenz würde diesen Test bestehen. Die visuelle Überprüfung - obwohl sie während des Debuggens etwas nützlich ist - ist fehleranfällig und für große Sätze unmöglich.

Eine bessere Lösung besteht darin, ein doppeltes Array zuzuordnen und es mit einem bekannten guten Algorithmus zu sortieren, dann jedes Element auf Gleichheit zu vergleichen.