Develop a highly modularized C++ program that will sort a set of numbers using a
ID: 3667624 • Letter: D
Question
Develop a highly modularized C++ program that will sort a set of numbers using a modified binary sort algorithm while maintaining a doubly linked sorted list. Use pointers to build the linked list. Give the user the option to view every step of the sorting process (this verbose option will print each step to the user’s monitor). Read the input from a file specified by the user. Leave the sorted output in a file, and inform the user the name of the file before exiting.
Here is a sample input file:
18 10 29 21 10 26 38 8 28 32 10 12 48 2 2 49 2 15 49 3 25 59 1 2
53 4 9 76 8 20 79 4 28 81 5 28 81 6 81 10 18 86 5 9 95 5 2
98 11 23 0 3 30 2 4 8 6 6 10 6 8 10 6 9 10 8 1 7 9 4 4
Do not remove any duplicates found.
A doubly linked list has pointers in both directions:
struct listMemb {
int value;
struct listMemb *leftPtr;
struct listMemb *rightPtr;
};
Consider a bisort of the following data: 44 55 12 42 94 18 67
Let h be a pointer to the first (head) element of the list. Let t be a pointer to the last (tail) of the list. Let m be a pointer to the approximate middle of the list. Let x be the current input value.
Initially h => (points to) NULL, t => NULL, and m => NULL.
Read x = 44
Element #: 1 Value: 44
h => element 1
t => element 1
m => element 1
Read x = 55
Element #: 1 2 Value: 44 55
h => element 1
t => element 2
m => element 1
Read x = 12
Element #: 1 2 3
Value: 12 44 55
h => element 1
t => element 3
m => element 2
Read x = 42
Element #: 1 2 3 4
Value: 12 42 44 55
h => element 1
t => element 4
m => element 2
Read x = 94
Element #: 1 2 3 4 5
Value: 12 42 44 55 94
h => element 1
t => element 5
m => element 3
Read x = 18
Element #: 1 2 3 4 5 6
Value: 12 18 42 44 55 94
h => element 1
t => element 6
m => element 3
Read x = 67
Element #: 1 2 3 4 5 6 7
Value: 12 18 42 44 55 67 94
h => element 1
t => element 7
m => element 4
Algorithm:
Step 1: set h, t, and m to point to the first element read Step 2: if x < h->value, then add x to the list prior to h, set h to point to the new element, and adjust m Step 3: else if x > t->value, then add x to the end of the list, set t to point at the new element, and adjust m Step 4: else if x < m->value, insert x somewhere between h and m, and adjust m Step 5: else (if x > m->value), insert x somewhere between m and t, and adjust m Step 6: go to step 2 and repeat the process until all data have been sorted Note: if you encounter a duplicate x, add a new one.
The goal is to sort a list (with possible duplicates included in the input AND output) in ascending order. Here is some basic pseudocode:
while more data to read
read input
if input is <= the head pointer’s data, then
insert at head of queue
else if input is >= the tail pointer’s data then
insert at tail of queue
else
if input < the mid pointer’s data, then
insert somewhere in the first half of the queue
else
insert somewhere in the second half of the queue
end if
end if, else if, else
end while
To insert in the first half of the queue begin at the mid pointer and search left; to insert in the second half of the queue begin at the mid pointer and search right.
To compute the mid pointer at the end of each read and insertion: keep track of the number of entries in the queue: n. divide n by 2 (both as integers so any remainder is discarded): n / 2 = m starting at the head and find the mth entry in queue; put its address into the mid pointer.
Explanation / Answer
As node in a doubly linked list has two fields, prev and next, pointing to the previous node and the next node, it is good enough for representing a binary tree. We can use these fields to build a binary search tree and reconstruct a sorted doubly linked list as the binary search tree is traversed with inorder.
Pseudo code as below:
static NodePTR head1, tail1;
void TraverseTree(NodePTR root)
{ NodePTR work;
if (root != NULL)
{ Traverse(root->LEFT);
work = root->RIGHT;
APPEND_NODE(root);
Traverse(work); }
}
Here two static variables, head1 and tail1, are set to NULL before calling TraverseTree().
Function TraverseTree() receives the current root pointer. If it is not NULL, the left subtree is traversed. Then, the pointer to root's right subtree is saved to work, the root is appended to the end of the doubly linked list with head and tail pointers head1 and tail1, and finally the right subtree pointed to by work is traversed. The pointer to the right subtree must be saved before the root is appended to the doubly linked list since macro APPEND_NODE destroys prev and next.
Check below code for reference:
class Node{
public:
char alphabet;
Node* prev;
Node* next;
void put_next(Node* node);
Node* Begin();
Node* End();
Node* GetFromIndex(int index, Node* node);
void DisplayAll();
void DisplayAllEnd();
// Move the pointer to end
void push_back(int value){
Node* tempNode = new Node();
tempNode->alphabet = value;
tempNode->prev = this->End();
this->End()->next = tempNode;
}
// Move the pointer to front
void push_front(int value){
Node* tempNode = new Node();
tempNode->alphabet = value;
tempNode->next = this->Begin();
this->Begin()->prev= tempNode;
}
void swap(int index1, int index2){
Node* tempNode = new Node();
tempNode = GetFromIndex(3,this);
}
// Allows select position
void insert(int index, int value, Node* &node){
Node* tempNode = new Node();
tempNode->alphabet = value;
//node->Begin();
for(int i = 0; i <= index; i++){
node = node->next;
}
tempNode->prev = node->prev;
node->prev = tempNode;
tempNode->next = node;
// Handle null case too.
tempNode->prev->next = tempNode;
}
Node* Node::Begin(){
if(this->prev != NULL){
this->prev->Begin();
}
else{
return this;
}
}
void DisplayAll(Node* node){
cout<<node->alphabet<<endl;
if(node->next != NULL){
DisplayAll(node->next);
}
}
// Main
int _tmain(int argc, _TCHAR* argv[])
{
char newChar;
Node* alphabetLinkedList = NULL;
alphabetLinkedList = new Node();
alphabetLinkedList->alphabet = 'a';
for(int i = (int)'a'; i <= (int)'z'; i++){
Node* tempNode = new Node();
tempNode->alphabet = (char)i;
alphabetLinkedList->put_next(tempNode);
alphabetLinkedList = tempNode;
}
insert(6,3, alphabetLinkedList);
alphabetLinkedList->Begin();
DisplayAll(alphabetLinkedList);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.