Question

The goal of this assignment is to reinforce sorting algorithms in C++. Specifically, the lab is to implement the shell sort. Please use lab13.cpp as your starting point. Read Chapter 13 before your lab to understand different sorting techniques. Shell Sort is a variation of Insertion Sort explained in this chapter. Here is another link to help you understand this Shell sorting technique: https://www.tutorialspoint.com/data structures_algorithms/shell_sort algorithm.htm

*********************lab13.cpp********************

#include <cstdlib>

#include <cassert>

#include <ctime> // used in initialization of random number generator

using namespace std;

template <typename T>

bool is_sorted (T* a, size_t size);

// precondition: a is not NULL

// returns: whether array a is sorted

template <typename T>

void shell_sort (T* a, size_t size);

// precondition: a is not NULL

// postcondition: a is sorted in non-decreasing order

int* create_array (size_t size);

// returns an array with size random integers

int main ()

{

size_t size = 1000;

int* a = create_array (size);

shell_sort (a, size);

assert (is_sorted (a, size));

delete a;

return EXIT_SUCCESS;

}

--------Please implement the shell sort functions. Thank You

Answer 1

#include <cstdlib>

#include<iostream>

#include <cassert>

#include <ctime> // used in initialization of random number generator

using namespace std;

template <typename T>

bool is_sorted (T* a, size_t size)

// precondition: a is not NULL

// returns: whether array a is sorted

{

    int i;

   

    // traverse the array

    for( i = 0 ; i < size - 1 ; i++ )

    {

        // if the array is not sorted

        if( a[i] > a[i + 1] )

            return false;

    }

       

    // if the array is sorted  

    return true;

}

template <typename T>

void shell_sort (T* a, size_t size)

// precondition: a is not NULL

// postcondition: a is sorted in non-decreasing order

{

    int gap, i, x, y;

    T m;

    // a big gap in the beginning, then keep on reducing it

    for (gap = size / 2 ; gap > 0; gap /= 2)

    {

        for (x = gap; x < size ; x += 1)

        {

            m = a[x];

            // untill the appropriate position for i th element of a is

            // found, shift the elements

            for (y = x; y >= gap && a[y - gap] > m; y -= gap)

            {

                a[y] = a[y - gap];

            }

            // m is placed in the appropriate posotion

            a[y] = m;

        }

    }

}

int* create_array (size_t size)

// returns an array with size random integers

{

    // create a new array

    int *arr = new int[size];

   

    int i;

   

   for( i = 0 ; i < size ; i++ )

        arr[i] = rand() % 100;

       

    return arr;

}

int main ()

{

    size_t size = 1000;

   

    int* a = create_array (size);

   

    shell_sort<int>(a, size);

   

    assert (is_sorted<int>(a, size));

   

    delete a;

   

    return EXIT_SUCCESS;

}

Sample Output

Process exited after 0.95031 seconds with return valuee Press any key to continue . . .