/*! \\file: msort_linked.h */ #include <iostream> #ifndef LIST_H #define LIST_H
ID: 3545270 • Letter: #
Question
/*! ile: msort_linked.h */
#include <iostream>
#ifndef LIST_H
#define LIST_H
struct Node{
int x;
Node* next;
};
void print_list(Node* list);
class List {
friend std::ostream& operator<<(std::ostream& fout, const List& rhs);
friend void print_list(Node* L);
public:
List():list(0){};
void insert_front(int x);
void remove_front();
void sort();
private:
Node* mergesort(Node* list);
Node* split(Node* L1);
Node* merge(Node* L1,Node* L2);
Node* list;
};
#endif
Provide comlete function definitions for the four public and private methods
1. Sort()
2. mergesot()
3. split()
4. merge()
Explanation / Answer
1.sort is a function in c++ standard library that takes two random-access iterators, the start and the end, as arguments and performs a comparision on the range of elements between the two iterators, front-inclusive and end-exclusive: [start, end)
2.Merge Sort is a technique in which we use the algorithm of divide and conquer.
The input array is first divided into smaller sub-arrays, which are sorted in turn and again merged to get the original array in a sorted manner
3.A sequence of calls to this function split str into tokens, which are sequences of contiguous characters separated by any of the characters that are part of delimiters.
On a first call, the function expects a C string as argument for str, whose first character is used as the starting location to scan for tokens. In subsequent calls, the function expects a null pointer and uses the position right after the end of last token as the new starting location for scanning.
To determine the beginning and the end of a token, the function first scans from the starting location for the first character not contained in delimiters (which becomes the beginning of the token). And then scans starting from this beginning of the token for the first character contained in delimiters, which becomes the end of the token. The scan also stops if the terminating null character is found.
This end of the token is automatically replaced by a null-character, and the beginning of the token is returned by the function.
Once the terminating null character of str is found in a call to strtok, all subsequent calls to this function (with a null pointer as the first argument) return a null pointer.
The point where the last token was found is kept internally by the function to be used on the next call (particular library implementations are not required to avoid data races).
4. a merge sort (also commonly spelled mergesort) is an o(n log n) comaprision based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.