You are not logged in. Please login at www.codechef.com to post your questions!

×

STL sort algorithm

Which sorting algorithm does the STL sort uses to sort elements? Is it always the same or different for different sets of data.

asked 02 Feb '16, 20:26

pwarriors's gravatar image

5★pwarriors
4815
accept rate: 10%

edited 02 Feb '16, 20:29


There are three methods under Sorting Algorithms for STL,following are :

a> sort. b> is_sorted. c> partial_sort.

you need to implement them according to the data given :

implementation methods for these three sorting algorithms are :

a> This function of the STL, sorts the contents of the given range. There are two version of sort() :

sort(start_iterator, end_iterator ) : sorts the range defined by iterators start_iterator and end_iterator in ascending order. sort(start_iterator, end_iterator, compare_function) : this also sorts the given range but you can define how the sorting should be done by compare_function.

b> partial_sort() sorts first half elements in the given range, the other half elements remain as they was initially. partial_sort() also has two variations:

partial_sort(start, middle, end ) : sorts the range from start to end in such a way that the elements before middle are in ascending order and are the smallest elements in the range. partial_sort(start, middle, end, compare_function) : sorts the range from start to end in such a way that the elements before middle are sorted with the help of compare_function and are the smallest elements in the range.

c> This function of the STL, returns true if the given range is sorted. There are two version of is_sorted() :

is_sorted(start_iterator, end_iterator) : Checks the range defined by iterators start_iterator and end_iterator in ascending order. is_sorted(start_iterator, end_iterator, compare_function) : It also checks the given range but you can define how the sorting must be done.

Hope it cleared out your query.

link

answered 04 Feb '16, 04:18

wanderlust727's gravatar image

2★wanderlust727
211
accept rate: 0%

edited 04 Feb '16, 04:19

thankyou...

(04 Feb '16, 11:33) archit9102★
link

answered 02 Feb '16, 20:34

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

link

answered 02 Feb '16, 21:44

shuboy2014's gravatar image

2★shuboy2014
112
accept rate: 0%

It uses Introsort which is a combination on heap sort and quick sort.Worst case complexity is O(NlogN)

Actually if you are looking for a standard there's no requirement for a particular algorithm but it has to be stable. So , one might say it is implementation defined.

link

answered 02 Feb '16, 22:23

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

It uses Introsort which is a combination on heap sort and quick sort.Worst case complexity is O(NlogN)

Actually if you are looking for a standard there's no requirement for a particular algorithm but it has to be stable and must has a complexity O(nlogn). So , one might say it is implementation defined.

link

answered 02 Feb '16, 22:23

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

edited 02 Feb '16, 22:24

it uses intro sort,a combination of quick and heap sort. you can also use "qsort". check this function here for more details http://www.cplusplus.com/reference/cstdlib/qsort/

link

answered 04 Feb '16, 13:26

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,918
×1,664
×1,491
×801
×279
×159

question asked: 02 Feb '16, 20:26

question was seen: 1,430 times

last updated: 04 Feb '16, 13:26