- Forum
- General C++ Programming
- sort option needed
sort option needed
which sort (bubble,quick, merge) option best suited here?
1)A list sorted except for one item, which is in wrong place? recursive merge sort??
1)A list sorted except for one item, which is in wrong place? recursive merge sort??
shellsort, or insertion sort, are very well suited for nearly sorted lists that have had a couple of edits since last pass. Shell is no better if its only 1 item out of order, but its notably better if you have a few, even like 1% of a million or so.
if you KNOW you have this situation, you can also write something much smarter than even these.
of the 3 subpar choices given, probably merge, which you would split the list where the new element belongs and put it on the end of one of the 2 piles and reassemble.
if you don't know where the one item is located, you would have to find it first to do that. Note that you can just use the merge piece of mergesort, if you coded it that way. Merge alone just looks at the end of 2 containers, picks one of the values, removes it from where it was and puts into the target, until all items consumed. It does not 'sort' a scrambled list, but it can/does build a new sorted list from 2 sorted lists, so if you can craft your code to slice in the right spot, you can use this. I don't recall exactly if the recursive MS has the merge function split out, though.
are you trying to solve a dumb test question, or an actual problem here?
if you KNOW you have this situation, you can also write something much smarter than even these.
of the 3 subpar choices given, probably merge, which you would split the list where the new element belongs and put it on the end of one of the 2 piles and reassemble.
if you don't know where the one item is located, you would have to find it first to do that. Note that you can just use the merge piece of mergesort, if you coded it that way. Merge alone just looks at the end of 2 containers, picks one of the values, removes it from where it was and puts into the target, until all items consumed. It does not 'sort' a scrambled list, but it can/does build a new sorted list from 2 sorted lists, so if you can craft your code to slice in the right spot, you can use this. I don't recall exactly if the recursive MS has the merge function split out, though.
are you trying to solve a dumb test question, or an actual problem here?
Last edited on
Peter87 has an alternative method to the sorts you name, leo, in your other thread.
https://cplusplus.com/forum/general/284978/#msg1236092
https://cplusplus.com/forum/general/284978/#msg1236092
I am trying to find the most ideal sort among these (bubble,quick, merge), for the above scenario?
The notion of "the most ideal sort" is really subject to each individual case (amount of data) and type of container. There is no "one answer fits all cases."
This sounds more and more like some fancy froo-froo class exercise, nearly completely devoid of any real world application.
This sounds more and more like some fancy froo-froo class exercise, nearly completely devoid of any real world application.
| This sounds more and more like some fancy froo-froo class exercise, nearly completely devoid of any real world application. |
I disagree a little on that. Frequently you have a sorted list and it can change, an update or insert, and need to be reordered; that is a real world problem. What makes it classroomish instead of real world is the insistence on using those 3, none of which excel at this problem. Its like asking which is the best hearse, a ugo, a corvette, or a ford pickup? well the ford can do it, but yeehaw... its inappropriate. Maybe the goal is to get them to reason out how they work to see why one could do it better, but why so limited... sigh.
Either way I stand by my answer: of those 3, an adapted mergesort. Yeehaw.
Last edited on
Well the first questions that comes to my mind are how do you know the list is sorted except for 1 item - and how did that 1 item get to be in the wrong place? Depending upon the circumstance, shouldn't that 1 item have been inserted into the correct place instead of being inserted into the wrong place? What's the real-world example of this?
edit an entry, say its sorted by name and name had a typo...
or, say you only need to sort to display it, so insert a few after last display, mark it dirty, display request, resort...
databases sort of work like the above. Its more like modify/insert/delete a few items over some block of time (sometimes a full day of work, other times moments) and then commit them all at once ('sorting' them based off their (usually) hidden 'index' fields, not exactly but similar).
or, say you only need to sort to display it, so insert a few after last display, mark it dirty, display request, resort...
databases sort of work like the above. Its more like modify/insert/delete a few items over some block of time (sometimes a full day of work, other times moments) and then commit them all at once ('sorting' them based off their (usually) hidden 'index' fields, not exactly but similar).
Well if you're not using a self-sorting container (map/set/tree etc) then IMO you'd need performance stats as to why just doing a std::sort() etc is no good...
And if you're not using a self-sorting container, why not just insert in the right place instead of say at the end of a container for just 1 item? If delete can be expensive (such as a std::vector), then just mark the item as deleted without actually removing the item. When inserting then treat the marked item as 'available to use' and for view etc ignore them. Then when required, do a 'compaction' of the container using 'erase-remove'.
But really in cases like this much depends upon the application....
And if you're not using a self-sorting container, why not just insert in the right place instead of say at the end of a container for just 1 item? If delete can be expensive (such as a std::vector), then just mark the item as deleted without actually removing the item. When inserting then treat the marked item as 'available to use' and for view etc ignore them. Then when required, do a 'compaction' of the container using 'erase-remove'.
But really in cases like this much depends upon the application....
std::sort is fine here. It quickly falls to an insertion sort in most implementations, which is strong for this problem.
the whys are implementation specific, as you said.
the whys are implementation specific, as you said.
Last edited on
The complexity of std::sort isn't totally outrageous, O(N·log(N)).
https://en.cppreference.com/w/cpp/algorithm/sort
<algorithm> has other C++ stdlib sorts available, std::partial_sort, std::stable_sort and a new one for C++20. std::ranges::sort.
Better to use the C++ library for most uses of sorting instead of relying on hand-rolled solutions that aren't as optimized as the compiler's implementations.
https://en.cppreference.com/w/cpp/algorithm/sort
<algorithm> has other C++ stdlib sorts available, std::partial_sort, std::stable_sort and a new one for C++20. std::ranges::sort.
Better to use the C++ library for most uses of sorting instead of relying on hand-rolled solutions that aren't as optimized as the compiler's implementations.
| George P wrote: |
|---|
| <algorithm> has other C++ stdlib sorts available, std::partial_sort, std::stable_sort and a new one for C++20. std::ranges::sort. |
The different sorts provided by the standard library are sort, stable_sort, partial_sort, partial_sort_copy and nth_element.
All of these have both std:: and std::ranges:: versions but that mainly affects the function interface. For example, with std::ranges::sort you can pass a std::vector<int> as a range directly as argument while with std::sort you would have to pass vector.begin() and vector.end() as two arguments.
Last edited on
| Better to use the C++ library for most uses of sorting instead of relying on hand-rolled solutions that aren't as optimized as the compiler's implementations. |
That is a good guideline: use the C++ Standard library unless you really know better.
If the OP is on algorithms course, has just been described the various sorts and was then asked the:
| find the most ideal sort among these (bubble,quick, merge), for the list sorted except for one item, which is in wrong place |
it should be obvious to look at the complexity of each three when data is as in that scenario.
I've seen the complexity described decades ago and can't remember any. OP should know the topic better.
PS. I presume that "the list" is not "std::list".
Last edited on
Topic archived. No new replies allowed.