Implementing Generic Algorithms

mgcadmin 07-05-2024

I want you to read through the following implementation of mergesort, and think about the reasoning behind why writing this particular algorithm in this particular way would be. I mean, it starts off with a caveat that if a certain operation cant be performed properly, the algorithm wont run in it's expected time. Why would we chance this when we know how to implement a gurantee'd O(nlogn) mergesort? Merge() isn't so bad, but mergesort() splits the list by explicit sublist creation! Again, why would we want to write mergesort in such a way?

 
//If this cant be done as an O(1) operation, then the algorithm
//wont run in O(nlogn) time.
template <class T>
void appendFirst(SortableList<T>& from, SortableList<T>& too) {
    int first = from.getFirst();
    from.pop();
    too.append(first);
}

template <class T>
void merge(SortableList<T>& front, SortableList<T>& back, SortableList<T>& result) {
    while (!front.empty() && !back.empty()) {
        if (front.getFirst() < back.getFirst()) {
            appendFirst(front, result);
        } else {
            appendFirst(back, result);
        }
    }
    while (!front.empty()) appendFirst(front, result);
    while (!back.empty()) appendFirst(back, result);
}

void mergesort(SortableList<T>& sq) {
    if (sq.size() <= 1)
        return;
    LinkedList<int> front, back;
    int e = sq.size()/2;
    while (sq.size() > e) appendFirst(sq, front);
    while (!sq.empty()) appendFirst(sq, back);
    mergesort(front);
    mergesort(back);
    merge(front, back, sq);
} 

The answer is adaptability. The above algorithm will sort any container which implements the methods defined in the following SortableList interface:

 
template <class T>
class SortableList {
    public:
        virtual bool empty() = 0;
        virtual int size() = 0;
        virtual void append(T info) = 0;
        virtual void pop() = 0;
        virtual T getFirst() = 0;
}; 

Now it doesn't matter if you're underlying structure is an array, or a linked list, the same implementation of mergesort can sort either one.

 
template <class T>
class ArrayList : public SortableList<T> {
    private:
        T *a;
        int max;
        int front;
        int back;
    public:
        ArrayList() {
            front = 0;
            back = 0;
            max = 512;
            a = new T[max];
        }
        void append(T info) {
            a[back++] = info;
            if (back > max) back = 0;
        }
        void pop() {
            front++;
            if (front > max) front = 0;
        }
        T getFirst() {
            return a[front];
        }
        int size() {
            return back - front;
        }
        bool empty() {
            return size() == 0;
        }
        void print() {
            for (int i = front; i < back; i++)
                cout<<a[i]<<" ";
            cout<<endl;
        }
};

template <class T>
class LinkedList : public SortableList<T> {
    private:
        struct node {
            T info;
            node* next;
            node(T i, node* n) {
                info = i;
                next = n;
            }
        };
        node* head;
        node* tail;
        int n;
    public:
        LinkedList() {
            head = nullptr;
            tail = nullptr;
            n = 0;
        }
        int size() {
            return n;
        }
        bool empty() {
            return head == nullptr;
        }
        void push(T info) {
            head = new node(info, head);
            n++;
        }
        void append(T info) {
            node* t = new node(info, nullptr);
            if (empty()) {
                head = t;
            } else {
                tail->next = t;
            }
            tail = t;
            n++;
        }
        void pop() {
            node* t = head;
            head = head->next;
            t->next = nullptr;
            n--;
            delete t;
        }
        T getFirst() {
            return head->info;
        }
        void print() {
            for (auto t = head; t != nullptr; t = t->next)
                cout<<t->info<<" ";
            cout<<endl;
        }
};

This is what makes OOP and generic programming such a wonderful combination. It makes following the "Don't repeat yourself" advice a breeze!

int main() {
    LinkedList<int> ll;
    ArrayList<int> al;
    for (int i = 0; i < 10; i++) {
        ll.push(rand() % 99);
        al.append(rand() % 99);
    }
    cout<<"Linked List: "<<endl;    
    ll.print();
    mergesort(ll);
    ll.print();
    cout<<"Array List: "<<endl;
    al.print();
    mergesort(al);
    al.print();
    return 0;
} 

max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./mergesort
 Linked List:
 79 42 95 5 41 69 55 23 72 28 
 5 23 28 41 42 55 69 72 79 95
 Array List:
 43 79 70 39 1 40 25 4 54 55
 1 4 25 39 40 43 54 55 70 79
max@MaxGorenLaptop:/mnt/c/Users/mgoren$ 

---