Shell Sort and Sort Verification

Question

I'm fairly new to coding and I've been wrestling with this code that will allow me to randomly generate a massive array of integers, select a specific shell sort, and then test if the array was sorted correctly.

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

I don't know what I'm doing wrong, the shell sort doesn't actually sort the array or at least it doesn't do a descending sort, and if the program does check to make sure the array is sorted correctly it won't display the message I want it to display.

Answer 1

The shellsort is broken. It seems to be attempting to sort the gap sequence seq[] when it should be sorting the value sequence arr[]. Additionally the gap sequence should be a series of values. For example:

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 sequence:

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

Knuth sequence:

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

Collectively the values of h at each call to hsort is your gap sequence. Alternately these can be precomputed and stored.

---

Testing the sequence for descending (or more accurately non-ascending) can be done with:

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

However, this test is insufficient for verifying algorithm correctness. Consider a function that simply sets all elements to a single value. The resultant sequence would pass this test. Visual inspection - while somewhat useful during debugging - is error prone and impossible for large sets.

A better solution is to allocate a duplicate array and sort it with a known good algorithm, then compare each element for equality.

Answer 2

I don't have a specific answer, but these are some quick debugging tips:

1 - run the code through clang-format. If you don't/can't install it on your computer, there's online formatters available such as http://format.krzaq.cc/

2 - compile your code with the clang compiler with all the warnings turned on. Again if you don't/can't install clang on your computer there's a few online sandboxes to play with. Why Clang? They made a big effort to give it very nice warning/error messages.

I did both, and this is what clang had to say about the program (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.

These might help - especially the last one!