Home > Enterprise >  C Sort rows of a 2D array, based on the first column using bubblesort
C Sort rows of a 2D array, based on the first column using bubblesort

Time:11-21

Disclaimer: These are all fake adresses it is just for learning purposes.

I want my list to be sorted based of the first columns which are the [i][0] and with that make the rest of the row ([i][j]) follow with the new sorted position column. Right now my code seems to be ONLY sorting the first columns but not making the whole the row follow with it to the new position the first columns has been given. Ive tried many ways but havent seem to find a solution.

Please help me!

/*
konst.txt includes following:

Stengren Lena Bokstavsgatan 10 27890 Stadköping
Osterblad Johan Grönskog 12A 10908 Ljushöjda
Broholme Reny Havstundav 8 36799 Hökänget 
Roholm Karol Stugsten 7 45892 Rågskog
Lindagren Erika Hjufjord 139 87834 Skogholma
*/

    string adresser[50][6];
    string input_file = "D:\\konst.txt";
    ifstream input_stream;
    int lastpos = 0;
    string temp;


    input_stream.open(input_file);

    for (int i = 0; i < 20; i  ) {
        for (int j = 0; j < 6; j  ) {
            input_stream >> adresser[i][j]; //Saves the columns and rows in the 2d array
            cout << adresser[i][j] << ' ';  //Writes out the whole list
        }
        cout << endl;
    }

    for (int i = 0; i < 50; i  ) { //Finds the last position for collumns
        if (adresser[i][0] == "") {
            lastpos = i;
            break;
        }
    }
    cout << "\n\n\n\n";


    for (int i = lastpos - 1; i > 0; i--) {
        for (int j = 0; j < i; j  ) {
            if (adresser[j][0] > adresser[j   1][0]) { //Sorts the array for ONLY the first collumns.
                    temp = adresser[j][0];
                    adresser[j][0] = adresser[j   1][0];
                    adresser[j][0] = temp;
                    
            }
        }
    }

Reminder of what the 2d array includes:

/*
Stengren Lena Bokstavsgatan 10 27890 Stadköping
Osterblad Johan Grönskog 12A 10908 Ljushöjda
Broholme Reny Havstundav 8 36799 Hökänget 
Roholm Karol Stugsten 7 45892 Rågskog
Lindagren Erika Hjufjord 139 87834 Skogholma
*/

what the code does:

/*
Broholme Lena Bokstavsgatan 10 27890 Stadköping
Lindagren Johan Grönskog 12A 10908 Ljushöjda
Osterblad Reny Havstundav 8 36799 Hökänget 
Roholm Karol Stugsten 7 45892 Rågskog
Stengren Erika Hjufjord 139 87834 Skogholma
*/

What i want it to do:

/*
Broholme Reny Havstundav 8 36799 Hökänget
Lindagren Erika Hjufjord 139 87834 Skogholma 
Osterblad Johan Grönskog 12A 10908 Ljushöjda
Roholm Karol Stugsten 7 45892 Rågskog
Stengren Lena Bokstavsgatan 10 27890 Stadköping
*/

CodePudding user response:

Arrays are not a good datatype to do what you are trying to do. It is good to take "words" from real life and use them in your code. What you are doing is sorting contacts, so make something that represents a contact first, e.g. a struct. From there build your code, (one function at a time, functions are great for naming things too) which then will become more readable and easier to understand. For example like this :

#include <fstream>
#include <functional>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <regex>

struct contact_info_t
{
    std::string first_name;
    std::string last_name;
    std::string address;
    std::string postal_code;
    std::string city;
};

// removed the "special" characters for now, seems code has some trouble with that
std::istringstream file_content
{
    "Stengren Lena Bokstavsgatan 10 27890 Stadkoping\n"
    "Osterblad Johan Gronskog 12A 10908 Ljushojda\n"
    "Broholme Reny Havstundav 8 36799 Hokanget\n"
    "Roholm Karol Stugsten 7 45892 Ragskog\n"
    "Lindagren Erika Hjufjord 139 87834 Skogholma\n" 
};

// load uses a regex to split up string, I think that's what causes the issues with special characters.
// but the bottom line is read your file and build a vector of structs from it. Not an array
auto load(std::istream& file)
{
    static const std::regex rx{ "(\\w )\\s (\\w )\\s (\\w \\s\\w )\\s (\\w )\\s (.*)" };
    std::smatch match;
    std::vector<contact_info_t> contacts;
    
    std::string line;
    while (std::getline(file,line))
    {
        if (std::regex_search(line,match,rx))
        {
            contact_info_t info;
            info.last_name = match[1];
            info.first_name = match[2];
            info.address = match[3];
            info.postal_code = match[4];
            info.city = match[5];
            contacts.push_back(info);
        }
    }

    return contacts;
}

// Since you can sort by multiple predicates (functions that return a bool)
// I made a generic sort function. It sorts pointers to the structs
// so that no data is move where it is not necessary
auto sort(const std::vector<contact_info_t>& contacts, std::function<bool(const contact_info_t* lhs, const contact_info_t* rhs)> predicate)
{
    std::vector<const contact_info_t*> sorted_contacts;
    for (const auto& contact : contacts) sorted_contacts.push_back(&contact);
    std::sort(sorted_contacts.begin(), sorted_contacts.end(), predicate);
    return sorted_contacts;
}

// show the sorted contacts, one struct at a time.
// that way it is impossible for columns to get mixed up
void show_sorted_contacts(const std::vector<const contact_info_t*>& sorted_contacts)
{
    for (const auto& contact : sorted_contacts)
    {
        std::cout << contact->last_name << " ";
        std::cout << contact->first_name << " ";
        std::cout << contact->address << " ";
        std::cout << contact->city << " ";
        std::cout << contact->postal_code << "\n";
    }
}

int main()
{
    auto contacts = load(file_content);
    auto contacts_sorted_by_last_name = sort(contacts, [](const contact_info_t* lhs, const contact_info_t* rhs)
    {
        return (lhs->last_name < rhs->last_name);
    });
    
    show_sorted_contacts(contacts_sorted_by_last_name);
}

CodePudding user response:

If you ask 10 C developers you will probably get 11 different answers of differing complexity and using greater or fewer features of the language. Here's my take that is only a few steps on from the OP's code.

If you want to keep all the information in a row together, then this is what classes or structs are made for, and indeed is a big part of what makes C different from C. You roll your own type (in this case the Record struct) which groups together all the name/address information into one single item. Structs that only have simple member variables can be copied without any extra code.

There are a couple more things to do. The OP is using cout and ifstream, and these can both handle strings, and numbers. They need a little help on dealing with our new Record type, and this is what the two stream operator overloads do for us. Finally, if we are going to sort we need to able to compare two Records: in this case alphabetically by family name, so we overload the '>' operator.

Now, instead of a 2D array of strings, we have a 1D array of Records.

#include <fstream>
#include <iostream>
#include <string>

//Create a structure to hold all the items for a name/address
struct Record
{
    std::string familyName;
    std::string firstName;
    std::string streetName;
    std::string streetNumber;
    long postCode{ 0 };
    std::string townName;
};

//Overloads for printing out a record ...
std::ostream& operator<<(std::ostream& os, const Record& r)
{
    os << r.familyName << " " << r.firstName << " " << r.streetName << " "
        << r.streetNumber << " " << r.postCode << " " << r.townName;

    return os;
}

//... and reading in a record
std::istream& operator>>(std::istream& is, Record& r)
{
    is >> r.familyName >> r.firstName >> r.streetName >> r.streetNumber >> r.postCode >> r.townName;
    return is;
}

//How to compare two records
bool operator>(const Record& lhs, const Record& rhs)
{
    return lhs.familyName > rhs.familyName;
}

int main()
{
    using namespace std;

    //Create any fixed-length array of Records
    Record records[20]; 
    
    //Load the name/address info
    //and keep a count
    ifstream ifs;
    ifs.open("konst.txt", ifstream::in);
    auto nRecords = 0;
    cout << "Input:\n";
    while(ifs.good() && nRecords<20)
    {
        Record& r = records[nRecords];
        ifs >> r;
        cout << r << "\n";
        nRecords  ;
    }
    //Perform the bubble sort
    for (int i = nRecords - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j  )
        {
            if( records[j] > records[j 1])
            {
                //Swap records
                Record tmp = records[j];
                records[j] = records[j   1];
                records[j   1] = tmp;
            }
        }
    }
    //Print out result
    cout << "\nSorted:\n";
    for (int i = 0; i < nRecords; i  )
    {
        cout << records[i] << "\n";
    }

    ifs.close();
}

And here are the results (my default locale doesn't decode ä or ö):

Input:
Stengren Lena Bokstavsgatan 10 27890 Stadk├╢ping
Osterblad Johan Gr├╢nskog 12A 10908 Ljush├╢jda
Broholme Reny Havstundav 8 36799 Hökänget
Roholm Karol Stugsten 7 45892 Rågskog
Lindagren Erika Hjufjord 139 87834 Skogholma

Sorted:
Broholme Reny Havstundav 8 36799 Hökänget
Lindagren Erika Hjufjord 139 87834 Skogholma
Osterblad Johan Gr├╢nskog 12A 10908 Ljush├╢jda
Roholm Karol Stugsten 7 45892 Rågskog
Stengren Lena Bokstavsgatan 10 27890 Stadk├╢ping
  • Related