In this article, we will discuss different ways to sort an array of structs in C++.
Table Of Contets
Problem Statement
In this case, we are given an array of structs, which needs to be sorted according to our requirements. Now, Lets consider a example in which you need to sort all persons in increasing order of their age. If ages are same then sort by alphabetical order of their names.
We will declare a struct person which will contain two attributes viz. name and age. Where, name will be of string type and age will be if integer type. Like this,
struct person {
std::string name;
int age;
// Constructor for the struct
person(std::string input_name, int input_age)
{
name=input_name;
age=input_age;
}
};
Then we will construct an array of person objects. Like this,
Frequently Asked:
person arr[] = {person("ram", 67),
person("kiran", 26),
person("raju", 14),
person("riya", 14),
person("chotu", 10)};
Now we need to sort this array by the age of each person i.e. using the second attribute of struct. If for two elements age is same, then they will be sorted by name attribute. After sorting the array contents should be like this,
10 chotu 14 raju 14 riya 26 kiran 67 ram
There are different ways to sort an array of structs. Let’s discuss them one by one.
Sorting array of structs using STL sort() in C++
The sort() in STL accepts 3 arguments. First two are the starting and ending address of the array that needs to be sorted. The last argument is the address of compare function, which will be used to compare the elements, while sorting the array.
Using sort() with a function as comparator
We will first declare the struct and then the compare function. The compare_person() function will accept two arguments and will compare them It will return true if the second argument is greater than the first one.
Best Resources to Learn C++:
Time Complexity: O(nlog(n))Space Complexity: O(1)
Example
#include <iostream>
#include <algorithm>
using namespace std;
// The struct 'person' contains name and age of person
struct person {
string name;
int age;
// Constructor for the struct
person(string input_name, int input_age)
{
name=input_name;
age=input_age;
}
};
// The function will return 1 if person2 > person1 else 0
bool compare_person(const person &person1, const person &person2)
{
if(person2.age > person1.age)
return 1;
if(person2.age == person1.age)
{
if(person2.name > person1.name)
return 1;
}
return 0;
}
int main()
{
// Initiating array of struct 'person' with elements
person arr[] = {person("ram", 67),
person("kiran", 26),
person("raju", 14),
person("riya", 14),
person("chotu", 10)};
size_t len = sizeof(arr)/sizeof(arr[0]);
// Calling sort() function with user defined compare function 'compare_person'
sort(arr, arr+len, &compare_person);
// Printing Output
for(int i=0;i<len;i++)
{
cout<<arr[i].age<<' '<<arr[i].name<<endl;
}
}
Output
10 chotu 14 raju 14 riya 26 kiran 67 ram
Using sort() with a Lambda function as comparator
In the above example, instead of using creating separate function for comparator, we can also use the lambda function as comparator. For example,
#include <iostream>
#include <algorithm>
using namespace std;
// The struct 'person' contains name and age of person
struct person {
string name;
int age;
// Constructor for the struct
person(string input_name, int input_age)
{
name=input_name;
age=input_age;
}
};
int main()
{
// Initiating array of struct 'person' with elements
person arr[] = {person("ram", 67),
person("kiran", 26),
person("raju", 14),
person("riya", 14),
person("chotu", 10)};
size_t len = sizeof(arr)/sizeof(arr[0]);
// Calling sort() function with user defined compare function 'compare_person'
sort(arr, arr+len, [](const person &person1, const person &person2){
int result = 0;
if( (person2.age > person1.age) ||
((person2.age == person1.age) &&
(person2.name > person1.name)))
{
result = 1;
}
return result;
});
// Printing Output
for(int i=0;i<len;i++)
{
cout<<arr[i].age<<' '<<arr[i].name<<endl;
}
}
Output:
10 chotu 14 raju 14 riya 26 kiran 67 ram
Sorting an Array od Structs Using Bubble sort algorithm
In this approach we will explicitly check each parameter while determining which object is greater. We will impliment bubble sort algorithm in bubble_sort() function.
Time Complexity: O(n^2)Space Complexity: O(n)
Example
#include <iostream>
using namespace std;
// The struct 'person' contains name and age of person
struct person {
string name;
int age;
// Constructor for the struct
person()
{}
person(string input_name, int input_age)
{
name=input_name;
age=input_age;
}
};
void bubble_sort(person* arr, int len)
{
person temp;
for (int i = 0; i < len; i++)
for (int j = 0; j + 1 < len - i; j++)
// Swaping if first person is logically
// greater than second person.
if (arr[j].age > arr[j + 1].age)
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
else if (arr[j].age == arr[j + 1].age &&
arr[j].name > arr[j + 1].name)
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
int main()
{
// Initiating array of struct 'person' with elements
person arr[] = {person("ram", 67),
person("kiran", 26),
person("raju", 14),
person("riya", 14),
person("chotu", 10)};
size_t len = sizeof(arr)/sizeof(arr[0]);
// Calling bubble_sort() function
bubble_sort(arr, len);
// Printing Output
for(int i=0;i<len;i++)
{
cout<<arr[i].age<<' '<<arr[i].name<<endl;
}
}
Output
10 chotu 14 raju 14 riya 26 kiran 67 ram
Summary
In this article, we learned to compare struct objects and sort the array of objects using STL function sort() and a naïve approach using bubble sort.