Develop a highly modularized C++ program that will sort a set of numbers using a
ID: 3677134 • 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. Do not remove any duplicates found. Need More info go to http://tinyurl.com/h6up5qx
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 22
53 4 9 76 8 20 79 4 28 81 5 28 81 6 81 10 18 86 5 9 95 5 20
98 11 23 0 3 30 2 4 8 6 6 10 6 8 10 6 9 10 8 1 7 9 4 4
Explanation / Answer
/*
* C++ Program to Implement Sorted Doubly Linked List
*/
#include<stdlib.h>
#include<iostream>
#include <fstream>
using namespace std;
int c = 0;
// linked list node structure
struct node
{
node *next, *prev;
int data;
}*head = NULL, *tail = NULL, *p = NULL, *r = NULL, *np = NULL;
// function to add element in doubly linked list in sorted form
void add(int x)
{
np = new node;
np->data = x;
np->next = NULL;
np->prev = NULL;
if (c == 0)
{
tail = np;
head = np;
p = head;
p->next = NULL;
p->prev = NULL;
c++;
}
else
{
p = head;
r = p;
if (np->data < p->data)
{
np->next = p;
p->prev = np;
np->prev = NULL;
head = np;
p = head;
do
{
p = p->next;
}
while (p->next != NULL);
tail = p;
}
else if (np->data > p->data)
{
while (p != NULL && np->data >= p->data)
{
r = p;
p = p->next;
if (p == NULL)
{
r->next = np;
np->prev = r;
np->next = NULL;
tail = np;
break;
}
else if (np->data <= p->data)
{
r->next = np;
np->prev = r;
np->next = p;
p->prev = np;
if (p->next != NULL)
{
do
{
p = p->next;
}
while (p->next !=NULL);
}
tail = p;
break;
}
}
}
}
}
// traverse doubly linked list forward
void traverse_tail()
{
node *t = tail;
while (t != NULL)
{
cout<<t->data<<" ";
t = t->prev;
}
cout<<endl;
}
// traverse linked list in reverse order
void traverse_head()
{
node *t = head;
while (t != NULL)
{
cout<<t->data<<" ";
t = t->next;
}
cout<<endl;
}
int main()
{
int i = 0, x;
ifstream inFile;
inFile.open("data.txt");
ofstream outFile;
outFile.open("sorted_data.txt");
while (!inFile.eof())
{
inFile>>x;
add(x);
cout<<"After insertion of "<<x<<": "<<endl;
traverse_head();
cout<<endl;
i++;
}
//cout<<" Traversing Doubly Linked List head first ";
//traverse_head();
// cout<<" Traversing Doubly Linked List tail first ";
//traverse_tail();
cout<<"Writing to output file: "<<endl;
node *t = head;
while (t != NULL)
{
outFile<<t->data<<" ";
t = t->next;
}
cout<<"Successfully writen to output file "<<endl;
}
/*
Output:
After insertion of 18:
18
After insertion of 10:
10 18
After insertion of 29:
10 18 29
After insertion of 21:
10 18 21 29
After insertion of 10:
10 18 21 29
After insertion of 26:
10 18 21 26 29
After insertion of 38:
10 18 21 26 29 38
After insertion of 8:
8 10 18 21 26 29 38
After insertion of 28:
8 10 18 21 26 28 29 38
After insertion of 32:
8 10 18 21 26 28 29 32 38
After insertion of 10:
8 10 10 18 21 26 28 29 32 38
After insertion of 12:
8 10 10 12 18 21 26 28 29 32 38
After insertion of 48:
8 10 10 12 18 21 26 28 29 32 38 48
After insertion of 2:
2 8 10 10 12 18 21 26 28 29 32 38 48
After insertion of 2:
2 8 10 10 12 18 21 26 28 29 32 38 48
After insertion of 49:
2 8 10 10 12 18 21 26 28 29 32 38 48 49
After insertion of 2:
2 8 10 10 12 18 21 26 28 29 32 38 48 49
After insertion of 15:
2 8 10 10 12 15 18 21 26 28 29 32 38 48 49
After insertion of 49:
2 8 10 10 12 15 18 21 26 28 29 32 38 48 49 49
After insertion of 3:
2 3 8 10 10 12 15 18 21 26 28 29 32 38 48 49 49
After insertion of 25:
2 3 8 10 10 12 15 18 21 25 26 28 29 32 38 48 49 49
After insertion of 59:
2 3 8 10 10 12 15 18 21 25 26 28 29 32 38 48 49 49 59
After insertion of 1:
1 2 3 8 10 10 12 15 18 21 25 26 28 29 32 38 48 49 4959
After insertion of 22:
1 2 3 8 10 10 12 15 18 21 22 25 26 28 29 32 38 48 4949 59
After insertion of 53:
1 2 3 8 10 10 12 15 18 21 22 25 26 28 29 32 38 48 4949 53 59
After insertion of 4:
1 2 3 4 8 10 10 12 15 18 21 22 25 26 28 29 32 38 4849 49 53 59
After insertion of 9:
1 2 3 4 8 9 10 10 12 15 18 21 22 25 26 28 29 32 3848 49 49 53 59
After insertion of 76:
1 2 3 4 8 9 10 10 12 15 18 21 22 25 26 28 29 32 3848 49 49 53 59 76
After insertion of 8:
1 2 3 4 8 8 9 10 10 12 15 18 21 22 25 26 28 29 3238 48 49 49 53 59 76
After insertion of 20:
1 2 3 4 8 8 9 10 10 12 15 18 20 21 22 25 26 28 2932 38 48 49 49 53 59 76
After insertion of 79:
1 2 3 4 8 8 9 10 10 12 15 18 20 21 22 25 26 28 2932 38 48 49 49 53 59 76 79
After insertion of 4:
1 2 3 4 4 8 8 9 10 10 12 15 18 20 21 22 25 26 2829 32 38 48 49 49 53 59 76 79
After insertion of 28:
1 2 3 4 4 8 8 9 10 10 12 15 18 20 21 22 25 26 2828 29 32 38 48 49 49 53 59 76 79
After insertion of 81:
1 2 3 4 4 8 8 9 10 10 12 15 18 20 21 22 25 26 2828 29 32 38 48 49 49 53 59 76 79 81
After insertion of 5:
1 2 3 4 4 5 8 8 9 10 10 12 15 18 20 21 22 25 2628 28 29 32 38 48 49 49 53 59 76 79 81
After insertion of 28:
1 2 3 4 4 5 8 8 9 10 10 12 15 18 20 21 22 25 2628 28 28 29 32 38 48 49 49 53 59 76 79 81
After insertion of 81:
1 2 3 4 4 5 8 8 9 10 10 12 15 18 20 21 22 25 2628 28 28 29 32 38 48 49 49 53 59 76 79 81 81
After insertion of 6:
1 2 3 4 4 5 6 8 8 9 10 10 12 15 18 20 21 22 2526 28 28 28 29 32 38 48 49 49 53 59 76 79 81 81
After insertion of 81:
1 2 3 4 4 5 6 8 8 9 10 10 12 15 18 20 21 22 2526 28 28 28 29 32 38 48 49 49 53 59 76 79 81 81 81
After insertion of 10:
1 2 3 4 4 5 6 8 8 9 10 10 10 12 15 18 20 21 2225 26 28 28 28 29 32 38 48 49 49 53 59 76 79 81 81 81
After insertion of 18:
1 2 3 4 4 5 6 8 8 9 10 10 10 12 15 18 18 20 2122 25 26 28 28 28 29 32 38 48 49 49 53 59 76 79 81 81 81
After insertion of 86:
1 2 3 4 4 5 6 8 8 9 10 10 10 12 15 18 18 20 2122 25 26 28 28 28 29 32 38 48 49 49 53 59 76 79 81 81 8186
After insertion of 5:
1 2 3 4 4 5 5 6 8 8 9 10 10 10 12 15 18 18 2021 22 25 26 28 28 28 29 32 38 48 49 49 53 59 76 79 81 8181 86
After insertion of 9:
1 2 3 4 4 5 5 6 8 8 9 9 10 10 10 12 15 18 1820 21 22 25 26 28 28 28 29 32 38 48 49 49 53 59 76 79 8181 81 86
After insertion of 95:
1 2 3 4 4 5 5 6 8 8 9 9 10 10 10 12 15 18 1820 21 22 25 26 28 28 28 29 32 38 48 49 49 53 59 76 79 8181 81 86 95
After insertion of 5:
1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 12 15 1818 20 21 22 25 26 28 28 28 29 32 38 48 49 49 53 59 76 7981 81 81 86 95
After insertion of 20:
1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 12 15 1818 20 20 21 22 25 26 28 28 28 29 32 38 48 49 49 53 59 7679 81 81 81 86 95
After insertion of 98:
1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 12 15 1818 20 20 21 22 25 26 28 28 28 29 32 38 48 49 49 53 59 7679 81 81 81 86 95 98
After insertion of 11:
1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 11 12 1518 18 20 20 21 22 25 26 28 28 28 29 32 38 48 49 49 53 5976 79 81 81 81 86 95 98
After insertion of 23:
1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 11 12 1518 18 20 20 21 22 23 25 26 28 28 28 29 32 38 48 49 49 5359 76 79 81 81 81 86 95 98
After insertion of 0:
0 1 2 3 4 4 5 5 5 6 8 8 9 9 10 10 10 11 1215 18 18 20 20 21 22 23 25 26 28 28 28 29 32 38 48 49 4953 59 76 79 81 81 81 86 95 98
After insertion of 3:
0 1 2 3 3 4 4 5 5 5 6 8 8 9 9 10 10 10 1112 15 18 18 20 20 21 22 23 25 26 28 28 28 29 32 38 48 4949 53 59 76 79 81 81 81 86 95 98
After insertion of 30:
0 1 2 3 3 4 4 5 5 5 6 8 8 9 9 10 10 10 1112 15 18 18 20 20 21 22 23 25 26 28 28 28 29 30 32 38 4849 49 53 59 76 79 81 81 81 86 95 98
After insertion of 2:
0 1 2 2 3 3 4 4 5 5 5 6 8 8 9 9 10 10 1011 12 15 18 18 20 20 21 22 23 25 26 28 28 28 29 30 32 3848 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 4:
0 1 2 2 3 3 4 4 4 5 5 5 6 8 8 9 9 10 1010 11 12 15 18 18 20 20 21 22 23 25 26 28 28 28 29 30 3238 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 8:
0 1 2 2 3 3 4 4 4 5 5 5 6 8 8 8 9 9 1010 10 11 12 15 18 18 20 20 21 22 23 25 26 28 28 28 29 3032 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 6:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 8 8 8 9 910 10 10 11 12 15 18 18 20 20 21 22 23 25 26 28 28 28 2930 32 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 6:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 8 8 8 9910 10 10 11 12 15 18 18 20 20 21 22 23 25 26 28 28 28 2930 32 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 10:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 8 8 8 9910 10 10 10 11 12 15 18 18 20 20 21 22 23 25 26 28 28 2829 30 32 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 6:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 8 8 899 10 10 10 10 11 12 15 18 18 20 20 21 22 23 25 26 28 2828 29 30 32 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 8:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 8 8 889 9 10 10 10 10 11 12 15 18 18 20 20 21 22 23 25 26 2828 28 29 30 32 38 48 49 49 53 59 76 79 81 81 81 86 95 98
After insertion of 10:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 8 8 889 9 10 10 10 10 10 11 12 15 18 18 20 20 21 22 23 25 2628 28 28 29 30 32 38 48 49 49 53 59 76 79 81 81 81 86 9598
After insertion of 6:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 8 888 9 9 10 10 10 10 10 11 12 15 18 18 20 20 21 22 23 2526 28 28 28 29 30 32 38 48 49 49 53 59 76 79 81 81 81 8695 98
After insertion of 9:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 8 888 9 9 9 10 10 10 10 10 11 12 15 18 18 20 20 21 22 2325 26 28 28 28 29 30 32 38 48 49 49 53 59 76 79 81 81 8186 95 98
After insertion of 10:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 8 888 9 9 9 10 10 10 10 10 10 11 12 15 18 18 20 20 21 2223 25 26 28 28 28 29 30 32 38 48 49 49 53 59 76 79 81 8181 86 95 98
After insertion of 8:
0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 8 888 8 9 9 9 10 10 10 10 10 10 11 12 15 18 18 20 20 2122 23 25 26 28 28 28 29 30 32 38 48 49 49 53 59 76 79 8181 81 86 95 98
After insertion of 1:
0 1 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 888 8 8 9 9 9 10 10 10 10 10 10 11 12 15 18 18 20 2021 22 23 25 26 28 28 28 29 30 32 38 48 49 49 53 59 76 7981 81 81 86 95 98
After insertion of 7:
0 1 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 788 8 8 8 9 9 9 10 10 10 10 10 10 11 12 15 18 18 2020 21 22 23 25 26 28 28 28 29 30 32 38 48 49 49 53 59 7679 81 81 81 86 95 98
After insertion of 9:
0 1 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 788 8 8 8 9 9 9 9 10 10 10 10 10 10 11 12 15 18 1820 20 21 22 23 25 26 28 28 28 29 30 32 38 48 49 49 53 5976 79 81 81 81 86 95 98
After insertion of 4:
0 1 1 2 2 3 3 4 4 4 4 5 5 5 6 6 6 6 678 8 8 8 8 9 9 9 9 10 10 10 10 10 10 11 12 15 1818 20 20 21 22 23 25 26 28 28 28 29 30 32 38 48 49 49 5359 76 79 81 81 81 86 95 98
After insertion of 4:
0 1 1 2 2 3 3 4 4 4 4 4 5 5 5 6 6 6 667 8 8 8 8 8 9 9 9 9 10 10 10 10 10 10 11 12 1518 18 20 20 21 22 23 25 26 28 28 28 29 30 32 38 48 49 4953 59 76 79 81 81 81 86 95 98
After insertion of 4:
0 1 1 2 2 3 3 4 4 4 4 4 4 5 5 5 6 6 666 7 8 8 8 8 8 9 9 9 9 10 10 10 10 10 10 11 1215 18 18 20 20 21 22 23 25 26 28 28 28 29 30 32 38 48 4949 53 59 76 79 81 81 81 86 95 98
Writing to output file:
Successfully writen to output file
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.