• Forum
  • Lounge
  • Article Review ~ In depth Tutorial On so

 
Article Review ~ In depth Tutorial On sort()

closed account (3qX21hU5)
All criticism is welcome especially if you see any mistakes on the code. Be warned I am probably not the best writer in the world and this is my first tutorial I have ever done so ;p.

This tutorial is aimed at beginners that have some knowledge of C++ but have yet to dabble much with the STL. This is part of the a series of tutorials I am putting together about algorithms and the usefulness of the STL.

Also I have yet to actually go through this more then once to do spelling corrections and all that so this is basically a first draft.

Let me know what you think thank you :)


Beginning with STL Algorithms
Tutorial #1 the sort() Function

By Zereo




Sort Function


First before we start lets take a quick look at how the function looks and what it does.

Here is what the function looks like in its default form, and with the optional third parameter. Don’t worry I will explain each parameter and more in a second, but first take a look at each of these functions and see if you can figure out what each parameter does.

Example 1~ std::sort(myvector.begin(), myvector.end())

Example 2~ std::sort(myvector.begin(), myvector.end(), myCompFuncion)

So lets go dig into these and figure out what each does and why it does it. First lets go over what everything is.

Found in ~ #include <algorithm>

Parameter 1 myvector.begin()~ The first parameter is where you will be putting a iterator(Pointer) to the first element in the range that you want to sort. The sort will include the element that the iterator points to.

Parameter 2 myvector.end() ~ The second parameter is almost like the first but instead of putting a iterator to the first element to sort you will be putting a iterator to the last element. One very important difference is that the search won’t include the element that this iterator points to. It is [First,Last) meaning it includes the first parameter in the sort but it doesn’t include the second parameter in the sort.

Parameter 3 myCompFunction() Optional ~ I will only give a brief description here, because I will explain this parameter in more detail later. The third parameter is used to define how you do the search. For example if you have a struct that has 3 different variables in it how does the function know which one to sort? Or how does it know how it should sort it? This is what this parameter is for. I will explain this more in a bit.

Function Return ~ This function doesn’t return anything because it alters the container directly through iterator (Pointers).






Array Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// sort() Example using arrays.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 7;

int main()
{
    int intArray[SIZE] = {5, 3, 32, -1, 1, 104, 53};

    //Now we call the sort function
    sort(intArray, intArray + SIZE);

    cout << "Sorted Array looks like this." << endl;
    for (size_t i = 0; i != SIZE; ++i)
        cout << intArray[i] << " ";

    return 0;
}


Things to know

When we use the sort function to sort a array our arguments will look a bit different then when we use it on a vector for example. In the example above when we pass in intArray as a argument we are telling the function to start the sort at the beginning of the array. If we wanted it to start the sort at the second element of the array we would do sort(intArray + 2, intArray + SIZE);. So when we do intArray + SIZE for the second argument we are telling the array to sort up to the last element in the array.




Sorting Vectors and other STL Containers Example

Warning: This example uses features that are only available in C++11 compilers. If you try this code and it doesn’t compile you most likely don’t have a C++11 compiler. Since the last time I checked Code::Blocks IDE comes with a C++11 compiler and you can enable it by going to settings->compiler->compiler settings->compiler flags-> and then you should see a checkbox that says something like Have g++ follow the C++11 ISO C++ language standard. Enable that and click ok and you should be good to go.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Vector Sorting Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
    // Warning this type of initialization requires a C++11 Compiler
    vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
    vector<string> stringVec = {"John", "Bob", "Joe", "Zack", "Randy"};

    // Sorting the int vector
    sort(intVec.begin(), intVec.end());

    for (vector<int>::size_type i = 0; i != intVec.size(); ++i)
        cout << intVec[i] << " ";

    cout << endl;

    // Sorting the string vector
    sort(stringVec.begin(), stringVec.end());

    // Ranged Based loops. This requires a C++11 Compiler also
    // If you don't have a C++11 Compiler you can use a standard
    // for loop to print your vector.
    for (string &s : stringVec)
        cout << s << " ";

    return 0;
}


Things to know:

First as you can see the sorting function works almost the same as on a array but we just have to pass our arguments a little differently. Since the first parameter in sort() accepts a iterator(pointer) to the first element we want to sort we can pass stringVec.begin() to it and it will start sorting at the first element in the vector. The same goes for stringVec.end() for the second parameter because remember stringVec.end() is a pointer to 1 past the last element in the container, and the sort function sorts up to but not including what we pass in as the second parameter.

You also probably noticed that the sort works on things other then numbers. When we printed out the vector of strings it gave us a nice and neat vector that holds the names in their alphabetical order.




The Third Optional Parameter.

The third parameter in the sort() function is actually a very useful feature. It allows up to define how the sort() function will actually perform the search. This parameter is optional because for basic types and containers it isn’t needed most of the time. But what if we wanted to change how the container was sorted by having it sort by descending instead of ascending? Or what if we had a container full of a special type of class we created and need to sort that container a special way? Well this is where the third parameter comes in.


Making it sort by descending order example. Warning: Uses C++11 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Vector Sorting Descending Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// We need this function to define how to sort
// the vector. We will pass this function into the
// third parameter and it will tell it to sort descendingly.
bool wayToSort(int i, int j) { return (i>j); }

int main()
{
    vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
    
    // Do not include the () when you call wayToSort
    // It must be passed as a function pointer or function object
    sort(intVec.begin(), intVec.end(), wayToSort);

    for (int i : intVec)
        cout << i << " ";
    
    return 0;
}



The Function

First lets look at the function. What we did is we created a function that will determine whether i > j if it is it will return true, if not it will return false every time it is called. The sort function will automatically assign a element to both i and j.

The function you make needs to have a return type of bool and must return only types that can be converted into bool.

So when we defined bool wayToSort(int i, int j) { return (i>j); } We are saying we wanted it to sort descending because i > j whereas ascending would be i < j.
Last edited on
closed account (3qX21hU5)
Second Halve




Sorting User Made Types.

For a lot of programs we aren’t storing just ints, strings, or doubles. Instead we are making complicated classes with that have multiple number and string members and storing them in a container. So when we want to sort that container of our class objects we need to define a special function that will tell the sort() function how it should sort them object.

So for my last example lets say we have a struct that represents a person and it looks like this.

1
2
3
4
5
6
struct Person
{
    string name;
    int age;
    string favoriteColor;
};


As you can see it has three members: name, age and color. Now lets say we have a program that has a vector full per Person objects, and we need a way to be able to sort them by their name, age or favorite color at certain points in the program.

One way would be to make a function for each different way of sorting. The example below is a program that will ask the user to enter 5 people’s names, ages, and favorite colors. It will then prompt a menu with different sorting options. Each of them sorting options sorts the container a certain way (By name, age or color).

Warning: Uses C++11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Complicated Types Sorting Example.
// Just a fun little program to demostrate sorting
// complicated types. It is by no means a complete program.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Person
{
    // Left out making a constructor for simplicity's sake.
    string name;
    int age;
    string favoriteColor;
};

// Sort Container by name function
bool sortByName(const Person &lhs, const Person &rhs) { return (lhs.name < rhs.name); }

// Sort Container by age function
bool sortByAge(const Person &lhs, const Person &rhs) { return (lhs.age < rhs.age); }

// Sort Container by favorite color
// We can just sort alphabetically and then it will group the
// color together.
bool sortByColor(const Person &lhs, const Person &rhs) { return (lhs.favoriteColor < rhs.favoriteColor); }

// A global const variable to hold how many people to ask for input for.
const unsigned numberOfPeople = 5;

int main()
{
    // Make a vector that holds 5 blank Person Objects
    vector<Person> people(numberOfPeople);

    // This will ask for user input to populate the container
    // with 5 different indivuals.
    for (vector<Person>::size_type i = 0; i != numberOfPeople; ++i)
    {
        cout << "Person #" << i + 1 << " name: ";
        cin >> people[i].name;

        cout << "Person #" << i + 1 << " age: ";
        cin >> people[i].age;

        cout << "Person #" << i + 1 << " favorite color: ";
        cin >> people[i].favoriteColor;
    }

    cout << "\n\n";

    // Keep looping until 4 is selected from the menu
    while (true)
    {
        cout << "How would you like to print them?" << endl
             << "\nEnter 1 to sort by name." << endl
             << "\nEnter 2 to sort by age" << endl
             << "\nEnter 3 to sort by color" << endl
             << "\nEnter 4 to exit \n" << endl;

        int menuChoice = 0;
        cin >> menuChoice;

        cout << endl;


        // Each case will sort the vector however the user specified
        // by using the sort() function and the functions we created.
        switch (menuChoice)
        {
            case 1:
                sort(people.begin(), people.end(), sortByName);
                for (Person &x : people)
                {
                    cout << "Name: " << x.name << endl
                         << "Age: " << x.age << endl
                         << "Color: " << x.favoriteColor << "\n\n";
                }
                break;

            case 2:
                sort(people.begin(), people.end(), sortByAge);
                for (Person &x : people)
                {
                    cout << "Name: " << x.name << endl
                         << "Age: " << x.age << endl
                         << "Color: " << x.favoriteColor << "\n\n";
                }
                break;

            case 3:
                sort(people.begin(), people.end(), sortByColor);
                for (Person &x : people)
                {
                    cout << "Name: " << x.name << endl
                         << "Age: " << x.age << endl
                         << "Color: " << x.favoriteColor << "\n\n";
                }
                break;

            case 4:
                cout << "Now exiting have a good day!" << endl;
                return 0;


            default:
                cout << "Error bad input! Please try again" << endl;
                break;
        }
    }

    return 0;
}



Things to know

That was actually a pretty large program and sadly I won’t have space to go through it all. I will however explain a bit about the functions we just made.


The Functions

Lets look at the sortByName() function as a example.

1
2
3
4
bool sortByName(const Person &lhs, const Person &rhs) 
{ 
    return (lhs.name < rhs.name);
}


This function is actually very similar to the one we just made before except for we changed two things. We changed the parameter types from int to type Person, and we also changed the return calculation a bit.

First let’s go over the change to the parameters.

The reason why we had to change the parameters from int to type Person, is because the container we are sorting is of type vector<Person>. And in order to be able to call the equation lhs.name < rhs.name the parameters would have to be of type Person.

Secondly we changed the return equation to (lhs.name < rhs.name). Can you guess what this equation is asking? Remember that both lhs and rhs are pointing to a separate element in the container (Like lhs is element 1 and rhs is element 2). So when we say lhs.name we are telling it to access element 1’s object and then access that objects name member. The same goes for rhs.name but is it accessing element 2’s object instead. So when we say to return lhs.name < rhs.name we are asking it is rhs’s object’s name less then rhs’s objects name.



Well that is all for this tutorial, I hope this helped anyone reading it. If you have any comments (Especially on any mistakes) on the article/tutorial please let me know I enjoy any type of feedback good or bad.

The same goes for any questions, if you don’t understand anything or the way I explained something didn’t make sense (Very likely ;p) please let me know through a reply here or through a PM. I would be glad to help answer any questions you have.

If this tutorial doesn’t totally bomb I might write a series of tutorial/articles aimed at beginners on the many uses of the STL algorithms.

Thanks for reading

~ Zereo
Last edited on
closed account (18hRX9L8)
Wow this is so interesting! Now I can have fun trying this out! This just made my life of sorting things 5x easier.

THANK YOU AND LOVE YOU!
closed account (3qX21hU5)
Thanks glad you liked it, let me know if you found anything that was a error or anything that was hard to understand or explained incorrectly.
I think operator< deserves a mention before you touch the user-defined comparison functors.

std::begin/std::end could be nice to mention since they work the same for C-style arrays and for vectors and other C++ containers.

the "complicated example" is probably too complicated at that step of the tutorial.

Speaking of structs with multiple members, a proper strict-weak-ordering comparison functor / operator< is worth showing (either return tie(lhs.a, lhs.b, lhs.c) < tie(rhs.a, rhs.b, rhs.c); or the pre-C++11ish return lhs.a < rhs.a ? true : lhs.b < rhs.b ? true : lhs.c < rhs.c ? true : false; if I didn't mix that up)

and of course there's a ton of things to write about fuctors, binds, lambdas, etc, depending on how much you wish to tell.

in another dimension, there are stable_sort, partial_sort, nth_element, and other important see-also's

By the way, the parentheses around expressions in return statements are unnecessary (and might be confusing, since it makes it look like a function call).
Cubbi, your second example is invalid. You should only go to second step if first values are equal (to break the tie)
Your code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct foo
{
    int a,b;
};

bool operator<(foo lhs, foo rhs)
{
    return lhs.a < rhs.a ? true : lhs.b < rhs.b ? true : false;
}
int main()
{
    foo x = {2, 3};
    foo y = {3, 2};
    std::cout << (x < y) << std::endl << (y < x);
}
1
1

return lhs.a != rhs.a ? lhs.a < rhs.a : lhs.b != rhs.b ? lhs.b < rhs.b : lhs.c != rhs.c ? lhs.c < rhs.c; Correct example.

And I think std::less, std::greater and others is worth mentioning, however I don't think those who uses this tutorial will find it useful yet.
Last edited on
std::begin/std::end could be nice to mention since they work the same for C-style arrays and for vectors and other C++ containers.

Damn right. So your array sorting example could have a C++11 variant:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    int intArray[] = {5, 3, 32, -1, 1, 104, 53};

    //Now we call the sort function
    sort(begin(intArray), end(intArray));

    cout << "Sorted Array looks like this." << endl;

    for (int i: intArray)
        cout << i << " ";

    return 0;
}


http://en.cppreference.com/w/cpp/iterator/begin
http://en.cppreference.com/w/cpp/iterator/end

Style suggestions:
1) I like to order headers alphabetically when including them
2) I like to omit the return statement in main() ... it's not something meaningful to write return 0; over and over
3) I think you shouldn't be using namespace std;

If you consider 3) here are links you may want to include instead of explaining things yourself:
http://www.parashift.com/c++-faq/using-namespace-std.html
http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-a-bad-practice-in-c

Your "Sorting User Made Types" example is too long. Keep focused on what you want to show, don't build a menu. Source code examples in articles should be "optimized" for reading, and not for compiling, in my opinion.

And where are the lambdas?! :)

Finally, I wouldn't write a series of articles, if I were you. I would rather write a single, large article with a Contents area with links to the sections. I'm pretty sure it's allowed to add links in the header names but I didn't test, then you could have "jump buttons", like [next], [prev] and [index].

Contents:
Introduction
Sort function
Array Example
Sorting Vectors and other STL Containers Example

[p] [n] [i] Introduction // here, [p] links to Contents
...

[p] [n] [i] Sort function
...

[p] [n] [i] Array Example
...

[p] [n] [i] Sorting Vectors and other STL Containers Example
...


Edit: tested and it actually works.

<H3 ID="stuff_one"><A HREF="#stuff_two">[next]</A> Stuff One</H3>

<H3 ID="stuff_two"><A HREF="#stuff_one">[prev]</A> Stuff Two</H3>

Last edited on
@MiiNiPaa right I did mix it up, that's why I just use tie() for those.
tie()... looks like a handy one. Thanks for pointing that out! I confess to being, heretofore, mostly tuple-ignert.
closed account (3qX21hU5)
Wow thank you everyone for the replies and feedback.

@Cubbi Thank you for the suggestions, will be rewriting part of the tutorial to include std::begin and std::end along with a minor note about them. Will also be working on talking about operator<.

@Catfish Thank you for the suggestions. I like your style suggestions, especially the using namespace std; one. I figured I would make it as beginner friendly as possible, but now that you point it out you are right I shouldn't be promoting using it. Also thank you for the links on that will be sure to include them in the article.

Your "Sorting User Made Types" example is too long. Keep focused on what you want to show, don't build a menu. Source code examples in articles should be "optimized" for reading, and not for compiling, in my opinion.


Ya that was the one big part that I was debating on with myself. On one side since the tutorial is aimed mainly at beginners I wanted to have one semi complete program that that they could copy and paste and play with. But on the other side it is taking up a huge amount of real estate and might be unnecessary. I think what I might do is optimize it down to just showing how to sort complicated types and then include a attachment that they can download if they want a full program example.


And where are the lambdas?! :)


They will be coming ;p this is only the first draft of the article and have much to add to it.

Finally, I wouldn't write a series of articles, if I were you. I would rather write a single, large article with a Contents area with links to the sections.


Ohh nice I didn't think I could do that. That actually makes it much easier since as you said I can just make a large article and include a Contents area with links to each section. Thank you for the suggestion.


@MiiNiPa
And I think std::less, std::greater and others is worth mentioning, however I don't think those who uses this tutorial will find it useful yet.

That is actually a great idea. Maybe add in a quick mention about using them for the comparative parameter like sort(intVec.begin(), intVec.end(), std::greater<int>()); since that would be useful for beginners.

Thanks everyone for the suggestions again, will be working on doing updates and adding more the to article. After I feel everything is corrected and looks good will submit it here and then just do updates to the article itself and hopefully turn it into a whole article on using the STL algorithms.
Maybe you could add a brief paragraph explaining the type of algorithm that sort uses and its time complexity. For example, it uses is a blah blah optimized, blah blah quick sort algorithm with guaranteed time complexity of blah blah blah for blah of blah.
Alghorithm used by sort is implementation defined. Complexivity should not exceed O(N·log(N)) for sort() or O(N·log2(N)) for stable_sort() (If addititional memory is used, complexivity should not exceed O(N·log(N)) too)
Last edited on
@ Zereo: I think I said this before, but I really think you must begin with an introduction about iterators.

You must explain what iterators are used for, and how they relate to pointers (like your array example shows). If you do this, then I suggest giving a simple example of a function template you write yourself to demonstrate the iterator pattern in C++.

http://en.wikipedia.org/wiki/Iterator_pattern

For example, the function below works out-of-the-box with std::vector<int>, std::set<int>, std::list<int> and others, despite how little work was put into writing it.

1
2
3
4
5
6
7
8
9
10
11
template <typename ForwardIterator>
void printAll(ForwardIterator begin, ForwardIterator end)
{
    while (begin != end)
    {
        std::cout << *begin << ' ';
        ++begin;
    }

    std::cout << std::endl;
}


Lambda functions are really important -- in your example:
std::sort(myvector.begin(), myvector.end(), myCompFuncion)

myCompFuncion could be replaced with a lambda function.
I believe there is no need to made this tutorial into "Tutorial about everything in C++". Lambda functions deserve their own tutorial.
@ MiiNiPaa: this is where lambda's belong, in my opinion.

It shouldn't be too hard to explain how to declare a lambda to accept parameters, to capture variables and to return a value. Then using them becomes easy, just plug them into the algorithms. The small overhead is worth it... again in my opinion.
Lambda functions can be used in many cases. I think that it is better to create another small tutorial about lambdas and reference it from other articles: "Lambdas often used as comparator function (more about lambdas here)"
Last edited on
This is a nice and well defined tutorial.
I did not read the tutorial because even the first statement is invalid

Here is what the function looks like in its default form, and with the optional third parameter


There is no "default form" of std::sort and there is no "optional third parameter" in std::sort in C++. There are two overload functions std:;sort.
Last edited on
closed account (3qX21hU5)
Default form as in the one used most often by beginners who this tutorial is for and optional parameter as in you don't need to include it. Personally I feel its not really necessary to get to go into the details of how the function is defined since the tutorial is geared at beginners. You don't need to know the details of how it is defined to know how to use it. But thank you for your input.

Let me know if anyone else sees a problem with the way that is worded and I will change it.
Last edited on
Topic archived. No new replies allowed.