Sorting Two Sets of Data in Parallel Array

Question

I'm currently having a real difficult time trying to sort my array (I really need to work on this, I always have trouble sorting data).

So basically I have created a C++ struct that contains a "date" and "snowDepth" element. I have used bubblesort logic to sort the snowDepth element, which is awesome and that's exactly what I need. However, since the elements are separate, the dates don't change. How can I sort a parallel array??

Data should look like this:

  Snow Report  December 12 - 18
      Date            Base
       13             42.3
       12             42.5
       14             42.8
       15             43.1
       18             43.1
       16             43.4
       17             43.8

and mine looks like this:

    SNOW REPORT    December 12 - 18
=======================================
       DATE             DEPTH
        12              42.3
        13              42.5
        14              42.8
        15              43.1
        16              43.1
        17              43.4
        18              43.8

Notice how the dates aren't sorted along with the snowDepth element. How can I accomplish this?

Okay, thanks for all the comments guys!! Here is my code:

// Structure
struct Array
{
    int date;
    double snowDepth;

    void SnowData(int d, double sD)
    {
        date = d;
        snowDepth = sD;
    }
};

// Main Function
int main()
{
    /* *--------------------*
       |      VARIABLES     |
       *--------------------* */

    // Constant Variables
    const int NUM_ELEMENTS = 7;
    const int NUM_MONTHS = 12;

    // String, Numerical, and Boolean Variables
    string month;
    int startDate;
    int endDate;
    int a;
    int b;
    int flag = 0;
    double result;
    bool monthMatch = false;

    // Array Variables
    Array snowData[NUM_ELEMENTS];
    string name[NUM_MONTHS] = {"January", "February", "March",
                               "April",   "May",      "June",
                               "July",    "August",   "September",
                               "October", "November", "December"  };


    /* *--------------------*
       | USER  INSTRUCTIONS |
       *--------------------* */    

    cout << endl;
    cout << "This program will keep track of the local snow conditions for 7 days." << endl;
    cout << "This program will ask the user for the month, date range (must be 7 days)," << endl;
    cout << "and the inches of snow reported on that date.  The program will then sort" << endl;
    cout << "the data from least amount of snow reported to the most." << endl;
    cout << endl;


    /* *--------------------*
       |     USER PROMPT    |
       *--------------------* */

    // Prompt the user for the month
    cout << "Enter the full name of the month: ";
    cin >> month;

    // Prompt the user for the starting date
    cout << "Enter the starting date of the 7-day period: ";
    cin >> startDate;
    snowData[0].date = startDate;

    // Once the user enters the start date, run a loop to initialize the rest of the dates in snowData array
    for (int x = 1; x < NUM_ELEMENTS; x++)
        snowData[x].date = ++startDate;

    // Prompt the user for the ending date
    cout << "Enter the ending date of the 7-day period: ";
    cin >> endDate;
    cout << endl;

    // If the user does not enter the correct ending date (which is 7 days from the start date), loop will prompt the user again
    if (endDate != snowData[NUM_ELEMENTS - 1].date)
    {
        do
        {
            cout << "The end date entered is not 7 days from the start date. Try again." << endl;
            cout << "Enter the ending date of the 7-day period: ";
            cin >> endDate;
            cout << endl;

        } while (endDate != snowData[NUM_ELEMENTS - 1].date);

        int x = 0;

        // Once the user enters the correct ending date, prompt the user for the snow depth numbers
        for (int y = 0; y < NUM_ELEMENTS; y++)
        {
            cout << "Enter the depth of snow measured on " << month << " " << snowData[x].date << ": ";
            cin >> snowData[y].snowDepth;
            x++;
        }
    }

    // Once the user enters the correct ending date, prompt the user for the snow depth numbers
    else
    {
        int x = 0;

        for (int y = 0; y < NUM_ELEMENTS; y++)
        {
            cout << "Enter the depth of snow measured on " << month << " " << snowData[x].date << ": ";
            cin >> snowData[y].snowDepth;
            x++;
        }
    }

    /* *--------------------*
       |  SORTING & FORMAT  |
       *--------------------* */

    // Sorting logic in ascending order
    for (a = 1; (a <= NUM_ELEMENTS) && flag; a++)
    {
        flag = 0;

        for (b = 0; b < (NUM_ELEMENTS - 1); b++)
        {
            if (snowData[b + 1].snowDepth < snowData[b].snowDepth)
            {
                result  = snowData[b].snowDepth;                
                snowData[b].snowDepth = snowData[b + 1].snowDepth;                
                snowData[b + 1].snowDepth = result;

                flag = 1;
            }
        }
    }

    // Formatted Output
    cout << endl;
    cout << "    SNOW REPORT    ";
    cout << month << " " << snowData[0].date << " - " << snowData[6].date << endl;
    cout << "=======================================" << endl;
    cout << setw(11) << "DATE" << setw(18) << "DEPTH" << endl;

    for (int x = 0; x < (NUM_ELEMENTS); x++)
        cout << setw(10) << snowData[x].date << setw(18) << snowData[x].snowDepth << endl;

    cout << endl;
}

Answer 1

You could create a struct for a single date/snowDepth pair, and keep an array of such pairs. After you could add more fields there, and sort by whatever you like. The data will always be consistent.

By the way: why bubble sort? Quicksort is much faster.

Answer 2

Since both elements is in the same struct, the two elements should move together. Your array should be an array of structs. How do you have it configured now?

Answer 3

Update Added a std::map based example for good measure (see below)

I wouldn't work on sorting as much as on datastructures :)

Here is a sample that I wrote in order to brush-off the dust of my C++ skills :) Sorry if I threw in more than the kitchen sink.

Also note, that for this 'tivial' datatype you could probably use std::pair as the 'Report' struct and std::map as the container type, requiring substantially less manual coding, but I wanted to show you how things are done if you coded the struct manually:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

static struct Report 
{ 
    int date; 
    double base; 
    Report(int d, double b) : date(d), base(b) {} 

    bool operator<(const Report& rhs) const
    {
        return (date<rhs.date) || ((date==rhs.date) && (base<rhs.base));
    }

    friend std::ostream& operator<<(std::ostream& os, const Report& r)
    {
        os << "Report(" << r.date << ", " << r.base << ")";
    }
} theData[] = { 
       Report( 13, 42.3),
       Report( 12, 42.5),
       Report( 14, 42.8),
       Report( 15, 43.1),
       Report( 18, 43.1),
       Report( 16, 43.4),
       Report( 17, 43.8),
   };


int main(int argc, const char* args[])
{
    Report *const begin = theData;
    Report *const end   = theData+(sizeof(theData)/sizeof(*theData));

    // simpler container, take a copy for comparison
    std::vector<Report> simplerData(begin, end);

    // just sort it
    std::sort(begin, end);

    // VERIFY by printing to console
    std::cout << "Verify sorted array: " << std::endl;
    std::copy(begin, end, std::ostream_iterator<Report>(std::cout, "\n"));
    std::cout << "=====================" << std::endl;

    std::cout << "Verify unsorted copy:" << std::endl;
    std::copy(simplerData.begin(), simplerData.end(), std::ostream_iterator<Report>(std::cout, "\n"));
    std::cout << "=====================" << std::endl;

    // Sort that as well - for fun, reversed
    std::sort(simplerData.begin(), simplerData.end(), std::not2(std::less<Report>()));

    std::cout << "Verify reversed copy:" << std::endl;
    std::copy(simplerData.begin(), simplerData.end(), std::ostream_iterator<Report>(std::cout, "\n"));
    std::cout << "=====================" << std::endl;
}

Compile and run using:

g++ -o test test.cpp
./test

Output:

Verify sorted array: 
Report(12, 42.5)
Report(13, 42.3)
Report(14, 42.8)
Report(15, 43.1)
Report(16, 43.4)
Report(17, 43.8)
Report(18, 43.1)
=====================
Verify unsorted copy:
Report(13, 42.3)
Report(12, 42.5)
Report(14, 42.8)
Report(15, 43.1)
Report(18, 43.1)
Report(16, 43.4)
Report(17, 43.8)
=====================
Verify reversed copy:
Report(18, 43.1)
Report(17, 43.8)
Report(16, 43.4)
Report(15, 43.1)
Report(14, 42.8)
Report(13, 42.3)
Report(12, 42.5)
=====================

---

For completeness, here's what it would look like when using std::map as I suggested above. Note that ordering by keys is implicit:

namespace std // hacky, google Koenig lookup...
{
    template <class K, class V> static std::ostream& operator<<(std::ostream& os, const std::pair<K, V> p)
        { os << "[" << p.first << ", " << p.second << "]"; }
}

void static UsingStdMap()
{
    typedef std::map<int, double> Reports;
    typedef Reports::value_type Report;

    static const Report initializer[] = {Report(13,42.3),Report(12,42.5),Report(14,42.8),Report(15,43.1),Report(18,43.1),Report(16,43.4),Report(17,43.8)};
    Reports theMap(initializer, initializer+sizeof(initializer)/sizeof(*initializer));

    std::copy(theMap.begin(), theMap.end(), std::ostream_iterator<Report>(std::cout, "\n"));
}

Did I mention I'm a bit lazy? Hence the hack to display the items using stream operator. To use custom ordering, see here for example

Answer 4

Since you've asked this under a C++ tag, here's one way in C++:

typedef std::pair<Date, double> SnowReportItem;
std::vector<SnowReportItem> SnowReport;
struct sort_criteria {
    bool operator()(const SnowReportItem &a, const SnowReportItem &b)
    { return a.second < b.second; }
};

SnowReport.push_back(make_pair(Date("12 Feb 2011"), 42.5));
// similar ones for the others ...

std::sort(SnowReport.begin(), SnowReport.end(), sort_criteria);

Also, see this stackoverflow question.

EDIT: std::pair.second is not a function.

Answer 5

If your homework assignment is specifically about learning to write a sorting algorithm, replace this code:

// Sorting logic in ascending order
...
            result  = snowData[b].snowDepth;                
            snowData[b].snowDepth = snowData[b + 1].snowDepth;                
            snowData[b + 1].snowDepth = result;
...

with this:

// Sorting logic in ascending order
...
            Array tmp  = snowData[b];                
            snowData[b] = snowData[b + 1];                
            snowData[b + 1] = tmp;
...

If your assignment is not about learning to write a sort, use std::sort:

bool Array::operator<(const Array& rhs) const { return this->snowDepth < rhs.snowDepth; }
...
// Sorting logic in ascending order
std::sort(snowData, snowData+NUM_ELEMENTS);

P.s. Your data type Array is misnamed. It doesn't hold an array, it holds a single observation.

Answer 6

You're already storing the data in a struct, so the simplest thing would actually be to just define operator< and swap for your Array type.

struct Array
{
    int date;
    double snowDepth;

    void SnowData(int d, double sD)
    {
        date = d;
        snowDepth = sD;
    }

    friend bool operator<(const SnowData &a, const SnowData &b)
    {
        return a.date < b.date;
    }

    friend void swap(SnowData &a, SnowData &b)
    {
        using std::swap;
        swap(a.date, b.date);
        swap(a.snowDepth, b.snowDepth);
    }
};

// ...later... sort the array
std::sort(snowData, snowData + NUM_ELEMENTS);

Answer 7

You were so close! It's correct that you compare the snowDepth values of the array elements, but you shouldn't just re-arrange those values. Instead, you should re-arrange the entire Array value.

Instead of this:

result  = snowData[b].snowDepth;
snowData[b].snowDepth = snowData[b + 1].snowDepth;
snowData[b + 1].snowDepth = result;

Do this:

Array temp = snowData[b];
snowData[b] = snowData[b + 1];
snoData[b + 1] = temp;

That will move both the snowDepth value and the date value (because they're members of the same struct).