Question

We saw in class different sorting algorithms, and we generally assumed the input to be sorted wasj an array. Here, the provided input is an unordered linked list of n elements with integer values. We are interested in sorting this list in increasing order (smallest first), in O(n log n) worst case time, while using constant space (also called in-place sorting). Note that recursion requires additional space on the stack, so should EC330 Applied Algorithms and Data Structures for Engineers, Fall 2020 be avoided in this case.

You are provided with the following files: LNode.h, LNode.cpp, LSorter.h, LSorter.cpp, and main.cpp.

A linked list node, LNode, is implemented in LNode.h and LNode.cpp. The LSorter class with the sortList method are declared in LSorter.h. The sortList method, which you need to implement, is declared as follows:

class LSorter { public: LNode* sortList(LNode* head); };

This method accepts as input the head node of the list to be sorted, and returns the head node of the sorted linked list. Your implementation should be included in the LSorter.cpp file. You may add additional classes and/or methods as you see fit, but everything should be included in this file, and none of the other files may be modified.

Finally, the provided main.cpp file may be used to test your implementation. You may assume that your input consists of non-negative integers with a maximal value of 1,000,000. Modify and submit LSorter.cpp only. The submitted file should compile and run with the rest of the files. We will run it against large linked list and measure the run time.

Partial credit will be given for an in-place solution with a runtime that is worse than O(n log n).

LNode.h:

#ifndef LNode_h
#define LNode_h

#include <stdio.h>

class LNode {
public:
    int val;
    LNode* next;
    LNode(int x=0);
};

#endif /* LNode_h */

LNode.cpp:

#include "LNode.h"

LNode::LNode(int x) {
        val = x;
        next = nullptr;
    }

Lsorter.h:

#ifndef LSorter_h
#define LSorter_h

#include <stdio.h>
#include "LNode.h"

class LSorter {
public:
    LNode* sortList(LNode* head);
};

#endif /* LSorter_h */

Lsorter.cpp:

#include <algorithm>
#include "LSorter.h"
using namespace std;

LNode* LSorter::sortList(LNode* head){
        // Your code goes in here...
    
}

main.cpp:

#include <iostream>
#include "LNode.h"
#include "LSorter.h"

using namespace std;

int main(int argc, const char * argv[]) {
    
    LNode LNode1(5);
    LNode LNode2(1);
    LNode LNode3(7);
    LNode LNode4(13);
    LNode LNode5(2);
    LNode LNode6(9);
    
    LNode1.next = &LNode2;
    LNode2.next = &LNode3;
    LNode3.next = &LNode4;
    LNode4.next = &LNode5;
    LNode5.next = &LNode6;
    
    LSorter solution;
    LNode* head = solution.sortList(&LNode1);
    
    LNode* currnode = head;
    while (currnode != nullptr){
        cout << currnode->val << endl;
        currnode = currnode->next;
    }           

    return 0;
}

Answer 1

Working code implemented in C++ and appropriate comments provided for better understanding.

Here I am attaching code for all files:

• LNode.cpp
• LNode.hpp
• LSorter.cpp
• LSorter.hpp
• main.cpp

LNode.cpp:

#include "LNode.hpp"

LNode::LNode(int x)

{

val = x;

next = 0; //nullptr;

}

LNode.hpp:

#ifndef LNode_hpp

#define LNode_hpp

#include <stdio.h>

class LNode {

public:

int val;

LNode* next;

LNode(int x=0);

};

#endif /* LNode_hpp */

LSorter.cpp:

#include "LSorter.hpp"

#include "LNode.hpp"

#include <iostream>

LNode* LSorter::sortList(LNode* head)

{

int size=1;//size of list

int count = 0;//number of mergeSorts executed

int first_size;//size of first half

int second_size;//size of second half

LNode *end;

LNode *left;

LNode *right;

LNode *next;

//if the list has 0 or 1 elements, return the list

if (head == NULL || head->next == NULL)

{

return head;

}

while (count == 0 || count > 2)//if program doesn't enter second loop-- list sorted

{

count=1;

left=head;

end=0;

head=0;

//loop through array until end

while (left != NULL)

{

right=left;

second_size=size;

first_size=0;

count++;//keep track of number of Merge Sorts

//change right LNode and size of first half of list to split list

while (right != NULL && first_size < size)

{

first_size++;

right=right->next;

}

//move through both first list and second list, changing next LNode based on sorting conditions

while ((second_size > 0 && right != NULL) || first_size > 0)

{

//if first half empty, use next right value

if (first_size == 0)

{

next=right;

right=right->next;

second_size--;

}

//if second half empty, use next left value

else if (second_size == 0 || right == NULL)

{

next=left;

left=left->next;

first_size--;

}

//compare actual values of the LNodes

else if (right->val > left->val)

{

next=left;

left=left->next;

first_size--;

}

//move through

else

{

next=right;

right=right->next;

second_size--;

}

//update class variables of end

if (end != NULL)

{

end->next=next;

}

else

{

head=next;

}

//keep track of end of list by setting to next value

end=next;

}

//set values for next iteration of mergesort

left=right;

}

//when finished,set pointer to next value to NULL and update size of list

end->next=0;

size = size * 2;

}

return head;

}

LSorter.hpp:

#ifndef LSorter_hpp

#define LSorter_hpp

#include <stdio.h>

#include "LNode.hpp"

class LSorter {

public:

LNode* sortList(LNode* head);

};

#endif /* LSorter_hpp */

main.cpp:

#include <iostream>

#include "LNode.hpp"

#include "LSorter.hpp"

using namespace std;

int main(int argc, const char * argv[]) {

LNode LNode1(5);

LNode LNode2(1);

LNode LNode3(7);

LNode LNode4(13);

LNode LNode5(2);

LNode LNode6(9);

LNode1.next = &LNode2;

LNode2.next = &LNode3;

LNode3.next = &LNode4;

LNode4.next = &LNode5;

LNode5.next = &LNode6;

LSorter solution;

LNode* head = solution.sortList(&LNode1);

LNode* currnode = head;

while (currnode != nullptr){

cout << currnode->val << endl;

currnode = currnode->next;

}

return 0;

}

Sample Output Screenshots: