Question

In: Computer Science

C++ sort a file with 140 integers where only 20 integers maybe placed into memory at...

C++ sort a file with 140 integers where only 20 integers maybe placed into memory at any one time

Main idea: break data into blocks, sort blocks into runs, merge runs less. Call inFile1 our source file (the one with the initial 140 records to be sorted. You will also need an inFile2, and 2 other files outFile1 and outFile2. Break the file into blocks of size 20: in this case there will be 7 blocks ( 140/20 ) Sort the blocks by read a block, sort it, store in outFile1 read a block, sort it, store in outFile2 read a block, sort it, store in outFile1 ( in other words, sort a block and alternately place in the files outFile1, outFile2 ) By definition a run is a sorted block Note that each file outFile1 and outFile2 will have half of the runs Merge the runs Merge data from outFile1 and outFile2 to  inFile1 and inFile2. Merge the first run on outFile1 and the first run on outFile2, and store the result on inFile1: Read two records in main memory, compare, store the smaller on inFile1 Read the next record from either outFile1 or outFile2  the file that had its record moved/stored  to inFile1 Similarly merge the second run on outFile1 and the second run on outFile2, store the result on inFile2. Merge the third run on outFile1 and the third run on outFile2, store the result on inFile1... etc.    merging each run and storing the result alternatively on inFile1 and inFile2. At the end        inFile1 and inFile2 will contain sorted runs twice the size of the previous runs on outFile1 and outFile2 Now merge data from inFile1 and inFile2   to outFile1 and outFile2. Merge the first run on inFile1 and the first run on inFile2 and store the result on outFile1. Merge the second run on inFile1 and the second run on inFile2, store the result on outFile2 Etc, merge and store alternatively on inFile1 and inFile2. Repeat the process until only one run is obtained. This would be the sorted file

restrictions:

MUST use algorithms from sort_algorithms.t:

the algorithms may not be modified. - but you may assume an overloaded < operator exists. Thus you may remove the pointer to the function cmp ( obviously, the code will have to replace any reference to cmp, no puns intended, with < ) It is permissible to copy/paste any algorithms from sort_algorithms.t that you use to your own sort_alg.t Declare a variable MAX_MEM_SIZE, of type size_t. Initialize to 20 If you are really paying attention to the directions, you will realize that 2 arrays of 20 cannot both be in memory at the same time – depending on how you implement the above algorithm and which sort you use, you may need to break into blocks of size 10 a sample file to be sorted is provided.

Sort_algorithms.t

*****************************************************************************************

template

void mergesort1(T* arrayptr, const int& arraySize )

{

sortmerge1( arrayptr, arraySize, 0, arraySize - 1 );

}

*****************************************************************************************

template

void sortmerge1( T* arrayptr, const int& arraySize, int l, int r )

{

int mid, i, j, k;

if ( l < r )

    {

      mid = (r + l)/2;

      sortmerge1( arrayptr, arraySize, l, mid );

      sortmerge1( arrayptr, arraySize, mid + 1, r );

      T* temp = new T[ arraySize ];

      for ( i = mid + 1; i > l; i-- )

        temp[ i - 1 ]= arrayptr[ i - 1 ];

      for ( j = mid; j < r; j++ )

        temp[ r + mid - j ] = arrayptr[ j + 1 ];

      for ( k = l; k <= r; k++)

        arrayptr[k] = ( temp[i] < temp[j] ) ? temp[i++] : temp[j--];

    }

temp = 0;

delete [] temp;

}

*****************************************************************************************

template

void msSort( T* arrayptr, const int& arraySize )

{

T* copy = new T[ arraySize ];

int i;

for ( i = 0; i < arraySize; i++ )

    copy[i] = arrayptr[i];

mergesort2( copy, arrayptr, 0, arraySize - 1 );

}

*****************************************************************************************

template

void mergesort2( T* source, T* dest, int l, int r )

{

if ( l != r )

    {

      int mid = ( l + r )/2;

      mergesort2( dest, source, l, mid );

      mergesort2( dest, source, mid + 1, r );

      merge2( source, dest, l, mid, r );

    }

}

*****************************************************************************************

template

void merge2( T* source, T* arrayptr , int l, int mid, int r )

{

int i = l;

int j = mid + 1;

int k = l;

while ( ( i <= mid ) && ( j <= r ) )         // Compare current item from each list

    if ( source[ i ] < source[ j ] )          // Then i item comes first

      arrayptr[ k++ ] = source[ i++ ];

    else                                        // j item comes first

      arrayptr[ k++ ] = source[ j++ ];

                                      // Move what is left of remaining list

if ( i > mid )

    while ( j <= r )

      arrayptr[ k++ ] = source[ j++ ];

else

    while (i <= mid )

      arrayptr[ k++ ] = source[ i++ ];   

}

#endif

Solutions

Expert Solution

The C++ program is:

#include<bits/stdc++.h>

using namespace std;

struch Mmhn

{

int element;

int i;

};

void swap(Mhn* x,Mhn* y);

class Mh

{

Mhn* harr

int hsize;

public:

Mh(Mhn a[], int size);

void Mhify(int);

int left(int i) { return(2*i+1);}

int right(int i); .............................................................................................................

Remaining code is in pictures:This the total code requried to sort.


Related Solutions

C Language NO ARRAY UTILIZATION OR SORTING Create a .txt file with 20 integers in the...
C Language NO ARRAY UTILIZATION OR SORTING Create a .txt file with 20 integers in the range of 0 to 100. There may be repeats. The numbers must not be ordered/sorted. The task is to find and print the two smallest numbers. You must accomplish this task without sorting the file and without using arrays for any purpose. It is possible that the smallest numbers are repeated – you should print the number of occurrences of the two smallest numbers....
Run Solver.java, where 20 array instances of 1M random integers are sorted (using Insertion- sort and...
Run Solver.java, where 20 array instances of 1M random integers are sorted (using Insertion- sort and Heap-sort, respectively). Solver.java is given, however the two sorting algorithms of course are implemented by yourself. Report the time elapsed running Solver.java, using Insertion-sort, and Heap-sort, respectively. Based on your results, comment comparatively on time-efficiency of the two sorting algorithms ////// public class Solver {    public static void main(String[] args) { final int SIZE = 1000000; // 1 million final int Instances=20; int[][]...
C programing language A file "data.txt" contains only integers. Write a code to find average of...
C programing language A file "data.txt" contains only integers. Write a code to find average of all values and print the average How would you use execlp function to execute "ps –e –a –l" command char *dt = "The five boxing wizards jump quickly"; write a program to count frequency of each letter, ignore case. Print the letter and frequency of each letter. // 1A: . Ask the user to enter a password string, store it in pass. Password should...
External sort: Write an external merge sort in c++ that takes in an input file with...
External sort: Write an external merge sort in c++ that takes in an input file with 120 integers. You are allowed to hold a maximum of 20 integers in memory. You must create 2 files to process the integers and they must be sorted and placed in the original file.
(C++)Counting Sort: Write C++ codes for counting sort. The input array is A = {20, 18,...
(C++)Counting Sort: Write C++ codes for counting sort. The input array is A = {20, 18, 5, 7, 16, 10, 9, 3, 12, 14, 0}
The purpose here is to implement the QuickSort sorting algorithm to sort integers. Write a C...
The purpose here is to implement the QuickSort sorting algorithm to sort integers. Write a C program which accepts 1 command-line argument: the name of a text file which contains integers, one-per line. Your C program must be named project3. Your C program needs to implement the QuickSort algorithm to sort the integers read from the file specified on the command-line. Your QuickSort implementation must utilize the median-of-three algorithm for choosing a pivot, and BubbleSort any sub arrays with less...
(C++) Create a data file and name it "input.txt". manually save 10 integers into the file....
(C++) Create a data file and name it "input.txt". manually save 10 integers into the file. Write a program to read the data and calculate the average of events and odds, separately. Print out the average values.
PROVIDE CODE ONLY IN C++ / NO OTHER LANGUAGES PLEASE ADD SELECTION SORT/ INSERTION SORT/ AND...
PROVIDE CODE ONLY IN C++ / NO OTHER LANGUAGES PLEASE ADD SELECTION SORT/ INSERTION SORT/ AND BUBBLE SORT FUNCTION TO THIS PROGRAM #include <iostream> #include<vector> #include <algorithm >   #include <chrono>    #include <ctime> using namespace std; void bubblesSort() { // Please create Bubble Sort function// Make another for Selection Sort and  Insertion Sort } int main() { // empty vector vector<int> data; // data [0], data [1]... data[N-1] <-- end(data) // set of values to test N for (auto N :...
Using C, use mmap() to map a file to memory, and then search through it. For...
Using C, use mmap() to map a file to memory, and then search through it. For example, get and print out the first character of each line in the file: abc def ghi
This is c++ code. Create a file sort.cpp. to mix functions with the selection sort algorithm:...
This is c++ code. Create a file sort.cpp. to mix functions with the selection sort algorithm: ·Write a function int least(vector<string> strs, int start)to return the index of the smallest value in the vector. You are to assume there is at least one value in the vector. ·Write a function void selsort(vector<string> & strs) to use selection sort to sort the vector of strings. It is a worthwhile experiment to try leaving out the & and seeing that the vector...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT