# Interview Questions

# Sort in C++ standard template library

- November 14, 2017
- Posted by: Kamal Rawat
- Category: Algorithms C++

Two elements of complex data types are not directly comparable. Consider the student structure defined as below

struct Student { int rollNo; char name[25]; char grade; }; Student arr[MAX_NUM_STUDENTS];

Objects of Student type are not directly comparable. To sort array arr, we need to specify how one student compares with another student. If there are two applications, one to take attendance and another to arrange all students for convocation. For first application, students should be arranged in increasing order of their roll numbers, and for convocation application, students receive their degrees in decreasing order of their grades. If a and b are two students, comparison of first application is like

if(a.rollNo < b.rollNo)

And second application compares on the grade field

if(a.grade < b.grade)

For both applications, sorting logic remains the same, but comparisons are different.

Most libraries provide inbuilt support for sorting lists. They decouple comparison logic from sorting logic. Sorting logic is provided as part of library, and comparison logic can be optionally supplied as an extra parameter. We can specify our own comparator function if elements are not directly comparable using relational operator.

Like other languages, standard template library (STL) of C++ language comes with inbuilt implementation of sort function. An array of integers can be sorted using the library function sort as shown below:

int arr[] = {2, 5, 3, 1, 4, 9, 0, 8, 7, 6}; std::sort(arr, arr+10);

It receives two parameters, a pointer to first element of array and a pointer to end of array, and sort the array in ascending order by default.

To sort complex data type, a comparator function can be supplied as third argument to above sort function. Comparator function defines how to compare two elements of given data type. For two integer variables, comparator function is as simple as

bool compare(int a, int b) { return a<b; }

Comparator function of Student for attendance application is

bool Compare1(struct Student a, struct Student b) { return (a.rollNo < b.rollNo); }

It take two arguments of Student type and determine if first element is smaller than second or not. For attendance application, a Student is smaller (comes before in ascending order) when its roll number is less

than other. Similarly, comparator function for convocation application is

bool Compare2(struct Student a, struct Student b) { return (a.grade < b.grade); }

Below code sort and print array arr in sorted order for the two applications respectively:

int main() { Student arr[ ] = { {2, "Ram Chandra", 'C'}, {3, "Mohan Mehta", 'B'}, {4, "Moksha Rawat",'A'}, {1, "Ritambhara", 'C'}, {5, "Amit Verma", 'B'}}; // SORT USING Compare1 FUNCTION std::sort(arr, arr+5, Compare1); printArray(arr, 5); // SORT USING Compare2 FUNCTION std::sort(arr, arr+5, Compare2); printArray(arr, 5); }

If printArray function is defined as below:

void printArray(Student *arr, int n) { cout<<"\n----------------------------------\n"; for(int i=0; i<n; i++) cout << arr[i].rollNo << " " << arr[i].name << " " << arr[i].grade<<endl; }

Output:

---------------------------------------- 1 Ritambhara C 2 Ram Chandra C 3 Mohan Mehta B 4 Moksha Rawat A 5 Amit Verma B ---------------------------------------- 4 Moksha Rawat A 3 Mohan Mehta B 5 Amit Verma B 1 Ritambhara C 2 Ram Chandra C