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$
