shell_ex

%%writefile ShellSortEx.h

#ifndef SHELLSORTEX_H
#define SHELLSORTEX_H
#include "ISortEx.h"

template<class T>
class ShellSortEx: public ISortEx<T>{
private:
    int *num_segment_list;
    int num_phases;

public:
    ShellSortEx(int *num_segment, int num_phases){
        this->num_phases = num_phases;
        this->num_segment_list = new int[num_phases];
        for(int idx=0; idx < num_phases; idx++)
            this->num_segment_list[idx] = num_segment[idx];
    }
    ~ShellSortEx(){
        delete []num_segment_list;
    }

    void sortSegment(T array[], int size,
            int segment_idx, int cur_segment_total,
            int (*comparator)(T&, T&))
    {
        //YOUR CODE HERE
        int current;
        int walker;
        T temp;
        current = segment_idx + cur_segment_total;
            while(current < size)
        {
            temp = array[current];
            walker = current - cur_segment_total;
            while((walker >= 0) && comparator(temp, array[walker]) < 0)
            {
                array[walker + cur_segment_total] = array[walker];
                walker -= cur_segment_total;
            }
            array[walker + cur_segment_total] = temp;
            current += cur_segment_total;
        }

    }
    /*
    shell_sort
    -----------
    num_segments:
         + The first must be 1, for examples: [1,3,7]
    */


    void sort(T array[], int size, int (*comparator)(T&,T&), int stride=1)
    {
        //YOUR CODE HERE
        for(int k = num_phases - 1; k >= 0; k--)
        {
            int numOfSeg = num_segment_list[k];
            for(int segment_idx = 0; segment_idx < numOfSeg; segment_idx++)
                sortSegment(array, size, segment_idx * stride, numOfSeg * stride, comparator);
        }
    }
};

#endif /* SHELLSORTEX_H */