473,246 Members | 1,563 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,246 software developers and data experts.

STL sort implementation

Hi,
I have a question regarding SGI STL sort implementation:
In case of equal elements, will they be output in the same order each
time I sort?
(I understand that it is not a stable sort, and by "same order" I mean
"same order
*each time I sort*"). Or is there a random number used in the splitter
for qsort?

Thanks

Feb 17 '06 #1
1 3441
Varun Kacholia wrote:
Hi,
I have a question regarding SGI STL sort implementation:
In case of equal elements, will they be output in the same order each
time I sort?
(I understand that it is not a stable sort, and by "same order" I mean
"same order
*each time I sort*"). Or is there a random number used in the splitter
for qsort?


(a) The SGI implementation is open for you to inspect. If I recall
correctly, it uses median of first, middle, and last entry and no random
selection takes place.

(b) An implementation is not required to use quick sort in std::sort(). In
fact, I think the SGI implementation uses introsort, a quick sort variation
with N log(N) worst case.

(c) Whether std::sort() produces deterministic outcomes for equal keys, is
up to the implementation. If you need that gaurantee, your options include:
(a) coding for a specific implementation for which you know what happens,
or (b) using std::stable_sort().
Best

Kai-Uwe Bux
Feb 17 '06 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

40
by: Elijah Bailey | last post by:
I want to sort a set of records using STL's sort() function, but dont see an easy way to do it. I have a char *data; which has size mn bytes where m is size of the record and n is the...
12
by: Eva | last post by:
Hi, I try to implement quick sort. I sort vectors by their first value. 10 2 3 4 9 3 5 6 10 4 5 6 must be 9 3 5 6 10 2 3 4 10 4 5 6 The prog works great on maybe 500 vectors, but I have an...
20
by: Xah Lee | last post by:
Sort a List Xah Lee, 200510 In this page, we show how to sort a list in Python & Perl and also discuss some math of sort. To sort a list in Python, use the “sort” method. For example: ...
4
by: DancnDude | last post by:
I have a class that needs to have several different kinds of sorting routines on an ArrayList that it needs to conditionally do based upon the data. I have successfully created a class that...
1
by: Gunjan Garg | last post by:
Hello All, I am working to create a generic datagrid which accepts a datasource(ListData - This is our own datatype) and depending on the calling program customizes itself for sorting,...
3
by: Alexander Widera | last post by:
Hi, I have a problem with this code ... (see below) ... I want to sort an instance of MyList ... by MyData.Shortname ... Shortname is of the type string.... how can I sort the entries? Thank...
21
by: yeti349 | last post by:
Hi, I'm using the following code to retrieve data from an xml file and populate a javascript array. The data is then displayed in html table form. I would like to then be able to sort by each...
9
by: active | last post by:
Can you see why this does not sort the list? It displays OK but is not sorted Thanks for any help
11
by: Jeff Schwab | last post by:
Would std::sort ever compare an object with itself? I'm not talking about two distinct, equal-valued objects, but rather this == &that. The container being sorted is a std::vector. I've never...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, youll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.