Timeline for Quick Sort Implementation with iterators
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2019 at 6:18 | comment | added | AlexV | @L.F.: (Forgive me my bitterness) I forgot that we are in C++ here, where you cannot do something for the sake of doing it, because it might not be optimal ;-) I included your feedback on the complexity issue in the post. | |
| Oct 4, 2019 at 6:16 | history | edited | AlexV | CC BY-SA 4.0 |
added 541 characters in body
|
| Oct 4, 2019 at 2:44 | comment | added | L. F. | I am afraid I have to disagree. Quick sort isn’t suitable for non random access iterators. The time complexity will go beyond quadratic. | |
| Oct 3, 2019 at 22:57 | history | edited | AlexV | CC BY-SA 4.0 |
added 390 characters in body
|
| Oct 3, 2019 at 22:50 | comment | added | AlexV |
I wasn't able to find the reason why the standard dictates to only accept random access iterators in std::sort when looking at the draft. My best guess would be that it allows to use more sorting algorithms in the actual implementation, e.g. Wikipedia seems to hint towards a hybrid algorithm in the GCC.implementation.
|
|
| Oct 3, 2019 at 22:25 | comment | added | Aykhan Hagverdili |
The main reason why I assumed begin and end were random access iterators is that std::sort assumes the same.
|
|
| Oct 3, 2019 at 22:24 | comment | added | Aykhan Hagverdili |
using std::distance to check if the range has more than 1 element seems inefficient for bidirectional iterators. Perhaps an "increase check if end, increase check if end" approach would be better for bidirectional iterators, but I imagine that'd affect efficiency detrimentally for random-access iterators.
|
|
| Oct 3, 2019 at 22:19 | comment | added | Aykhan Hagverdili |
I understand the suggestion about using std::distance, but bidirectional iterators support operator++ and operator--, right? What is the point of using std::prev and std::advance?
|
|
| Oct 3, 2019 at 21:48 | history | answered | AlexV | CC BY-SA 4.0 |