I have tried looking for it on my own but I am unable to find it. Can anyone link me to or post the source code of std::sort?
I have tried looking for it on my own but I am unable to find it. Can anyone link me to or post the source code of std::sort?
The source code will vary from implementation to implementation, the only thing that is guaranteed is that the complexity should be O(n log n).
sort (C++) - Wikipedia, the free encyclopedia
How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.
The wiki linked in post #2 does point to one implementation if you just want to see an example, though.
My bad, how about the GNU version? I know wikipedia mentions the algorithms used but I just really wanna see the code in the flesh.
As I said, check Wiki's references; it actually points to the GNU std::sort implementation.
So start by downloading gcc source code and looking through it...
All problems in computer science can be solved by another level of indirection,
except for the problem of too many layers of indirection.
– David J. Wheeler
Lol if I was on Linux, where would that be? /usr/lib/algorithm? I am on my Nook at the moment.
For visual studio, it's in ...\include\algorithm in the program file directory for visual studio. For VS2005, it's a bit past 1/2 into the file.
The definition of std::sort() will be found via the header <algorithm> for a lot of implementations (aka compilers/library/head file bundle) since std::sort() is a template.Originally Posted by rcgldr
Since implementations often can't compile templates without the template definition inline, there is a pretty good chance the source for std::sort() will be in the header file <algorithm>, or some file #include'd by that header.
Whether the source code is useful, that's another question. There is no requirement that the definition of standard library functions be portable between compilers.
...or even remotely readable.
How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.
O_oCan anyone link me to or post the source code of std::sort?
Why do you want the source for `std::sort' in particular?
Soma
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
phantom, I've been reading Addison and Wesley's Accelerated C++ book and I'm doing the student grading assignment and they used the sort() function. It seems to work pretty well and I was just curious how the pros would sort something out.
I think it's fascinating that they took a hybrid approach, using introsort into insertion sort. I've been reading up on introsort and it's definitely something that I didn't code when I was taking underdivision CS. If anything, I think all we did was the basics. I think we did insertion sort, Idk. The only thing I really remember from that class was using a doubly linked list to make a text editor and then making a dictionary/spell-checker using a hashing algorithm which I thought was so cool because during development, I wrote a non-hash version and then a hash version and wow, the speed-up time was absolutely astounding.
That being said, I'm always interested in algorithms and I wanted to see what true C++ looked like and holy poop, it is so confusing. I mean, wow. I'm gonna look at it some more and then post back with all the questions I have. I also figure that this is a fantastic way to learn advanced C++ and extend my knowledge of algorithms. I really do wanna code for a living someday and this is something that I feel will help me get there and even if it doesn't, it's really fun to learn.
Another idea:
Create a program with only a single sort statement (and required lines to get it to compile), then step through the source and, at least in visual studio, you can step through std::sort.
You can even look at how it works when sorting your dummy input.
For VS2005 <algorithm>, based on the comment, sort() is // divide and conquer by quicksort.
In algorithm, sort() is the user called function. _sort() and the other functions that begin with _ are internal functions. The user called sort() has this header:
I'm not sure if you're familiar with templates. The class<...> is just use to allow generic typing for the parameters. In this case there's only one type, and microsoft / hp named it _RanIt which stands for random access iterator, which means it's some type of iterator for an array or vector of some type of element that can be compared using < (including an overloaded < operator) (otherwise the sort() with a pointer to a user specified compare function is used).Code:template<class _RanIt> inline void sort(_RanIt _First, _RanIt _Last)
Lol I am on Linux so no VS for me but I found the file in my /include/ directory, which, ironically enough, makes a lot of sense. I have been looking at the code and will post my dissection of it here for review.
