Develop a highly modularized C++ program that will sort a set of numbers using a
ID: 3682991 • 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 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
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.
****Please ADD comments if you can/possible Thanks!
Explanation / Answer
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
//creation of doubly linked list
struct listMemb
{
int value;
struct listMemb *leftPtr;
struct listMemb *rightPtr;
};
listMemb *h=NULL,*t=NULL,*m=NULL;
void bisort(int x[],int size)
{
for(i=0;i<size;i++)
{
while(x[i]!=NULL)
{
h->value=x[i];
t->value=x[i];
m->value=x[i];
if(x[i]< h->value)
{
h->value=x[i+1];
m->value=(h->value+t->value)/2;
}
elseif(x[i] >t->value)
{t->value=x[i+1];
m->value=(h->value+t->value)/2;
}
else if(x[i] < m->value)
{
insert (x[i],h->value,m->value);
}
elseif(x[i]>m->value)
{
insert(x[i],h->value,m->value);
}
}
}
int readdata()
{
ifstream infile;
infile.open("list.txt");
int [] array=new int[255];
int i=0;
while(infile.eof())
{
array[i]=infile;
i++;
}
return array;
}
}
int main()
{
listMemb M;
int ar[] =readdata();
sort(int [] ar);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.