//Implment insertion sort using smart pointers.
//You are not allowed to swap node values; instead, you are only
//allowed to change pointer addresses.
#include
#include
using namespace std;
class node {
public:
int value;
//node * next;
//node * previous;
shared_ptr next;
weak_ptr previous;
//node(int i) { value = i; next = previous = nullptr; }
node(int i) { value = i; }
//node() { next = previous = nullptr; }
node() {}
};
class doubly_linked_list {
public:
//node * head;
//node * tail;
shared_ptr head, tail;
//doubly_linked_list() { head = tail = nullptr; }
doubly_linked_list() {}
void make_random_list(int m, int n);
void print_forward();
void print_backward();
//***************************
//You need to implement insertion_sort following the
//special requirements.
void insertion_sort();
};
void doubly_linked_list::make_random_list(int m, int n) {
for (int i = 0; i < m; i++) {
//node * p1 = new node(rand() % n);
shared_ptr p1 = make_shared(rand() % n);
p1->previous = tail;
//if (tail != nullptr ) tail->next = p1;
if (tail) tail->next = p1;
tail = p1;
//if (head == nullptr) head = p1;
if (!head) head = p1;
}
}
void doubly_linked_list::print_forward() {
cout |