CODEWITHSUNDEEP
calgorithmsorting
bardockyo
bardockyo

Reputation: 1435

mergesort algorithm

First let me say that this is hw so I am looking for more advice than an answer. I am to write a program to read an input sequence and then produce an array of links giving the values in ascending order.

The first line of the input file is the length of the sequence (n) and each of the remaining n lines is a non-negative integer. The first line of the output indicates the subscript of the smallest input value. Each of the remaining output lines is a triple consisting of a subscript along with the corresponding input sequence and link values.

(The link values are not initialized before the recursive sort begins. Each link will be initialized to -1 when its sequence value is placed in a single element list at bottom of recursion tree)

The output looks something like this:

0  3  5
1  5  2
2  6  3
3  7  -1
4  0  6
5  4  1
6  1  7
7  2  0

Where (I think) the last column is the subscripts, the center is the unsorted array, and the last column is the link values. I have the code already for the mergeSort and understand how it works I am only just confused and how the links get put into place.

Upvotes: 1

Views: 486

Answers (1)

Spatarel
Spatarel

Reputation: 242

I used vector of structures to hold the three values of each line.

The major steps are:

  • initialize the indexes and read the values from the input
  • sort the vector by value
  • determine the links
  • sort (back) the vector by index

Here is a sketch of the code:

struct Element {
    int index;
    int value;
    int nextIndex; // link
}

Element V[N + 1];
int StartIndex;

V[i].index = i;
V[i].value = read_from_input;

sort(V); // by value

startIndex = V[0].index;
V[i].nextIndex = V[i + 1].index;
V[N].nextIndex = -1;

sort(V); // by index

Upvotes: 1

Related Questions