Sorting algorithm is a former featured article candidate. Please view the links under Article milestones below to see why the nomination was archived. For older candidates, please check the archive. | ||||||||||
|
This level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||
|
template <class iterator> void gnome(iterator first, iterator last){ // O(n^2) iterator pos = first; while (pos <= last) { if ((pos == first) || ((*pos) >= *(pos - 1))) ++pos; else { std::iter_swap(pos, pos+1); --pos; } } }
Is this a genuine question about the quality of your code? If so, I'd probably suggest posting on StackExchange or something. — Preceding unsigned comment added by 2605:6000:1522:400B:10FB:405:731E:8F1B (talk) 15:59, 4 October 2017 (UTC)
I'm surprised at not finding slowsort here. While it is one of the less serious kind of algorithms, it is interesting since it is, however slowly, steadily progressing to its goal (as opposed to, say, bogosort). The algorithm:
It is described at http://c2.com/cgi/wiki?SlowSort and was, according to that page, first published in the satyrical article "Pessimal algorithms and the simplexity of computations" by A. Broder and J. Stolfi, in ACM SIGACT News vol. 16 no. 7, pages 49--53, fall 1984. I haven't located that article yet, though. Both links given there are broken. —Preceding unsigned comment added by SQB (talk • contribs) 20:08, 26 July 2009 (UTC)
Stupid sort - This article was copied from the deleted Wikipedia article which sat in the "Stupid sort" page. -- A perfect demonstration how stupidity proliferates in the internet with the help and andorsement of wikipedia :-) 23:25, 6 February 2010 (UTC)
For example, the time complexity for bubble sort is listed as n2.
While its computational complexity (time + space) is on the order of n2 (2n2-2n), the worst case time complexity is not n2.
worst case time complexity (comparisons) for bubble sort is (n2/2) - (n/2). But they are all wrong. —Preceding unsigned comment added by 74.140.173.132 (talk) 05:57, 24 February 2010 (UTC)
the wrong is the thing —Preceding unsigned comment added by 203.110.243.22 (talk) 12:07, 20 November 2010 (UTC)
(n2/2) - (n/2) IS O(n2)
Should it be O(n log n) instead n log n in comparison table? —Preceding unsigned comment added by Conan (talk • contribs) 00:06, 9 May 2010 (UTC)
Comparison table states that its "memory" is log(n). But, as far as I know, quick sort is in-place sort. Even its own article said so: "...Coupled with the fact that quicksort is an in-place sort and uses no temporary memory...". —Preceding unsigned comment added by 85.222.169.174 (talk) 13:44, 4 June 2010 (UTC)
In the worst case, quicksort sorts a group of items in O(N2), where N is the number of items. If randomization is incorporated into the algorithm, however, the chances of the worst case actually occurring become diminishingly small, and on average, quicksort has a runtime of O(N*Log(N)). Other algorithms guarantee a runtime of O(N*Log(N)), even in the worst case, but they are slower in the average case. Even though both algorithms have a runtime proportional to N*Log(N), quicksort has a smaller constant factor - that is it requires C*N*Log(N) operations, while other algorithms require more like 2*C*N*Log(N) operations —Preceding unsigned comment added by Tarun telang (talk • contribs) 10:31, 11 June 2010 (UTC)
I find it rather ironic that this table does itself not appear to be sorted! The "exchanging" methods are kept together and are ordered alphabetically, but other than that the order seems to be pretty random. I am in favour of sorting this table according to Method and then name, but other options such as by average case complexity and then name also seem fine to me. It may be like a bit of a plug that Timsort has been placed at the top of this table. There seems to be less reason for it to appear in the table compared to some algorithms that are currently omitted.
Secondly, I'd also like to see a best case column added to the table. Then it would make sense to add other algorithms such as Binary Insertion Sort whose best case differs from normal Insertion Sort, but the average and worst cases are the same. It would also make sense to hilight the fact that bubble sort (amoung others) can be implemeneted with an O(n) best case. Several other algorithms such as Bitonic Merge Sort, Bingo Sort, Odd-Even Transposition Sort, Strand Sort, Squeeze Sort, and Order Sort to name a few, could also be added.
Malcolm —Preceding unsigned comment added by 118.92.109.220 (talk) 03:01, 13 June 2010 (UTC)
The linked file "File:SortingAlgoComp.png" has a very poor quality of information. There are some spelling mistakes "Tourament" (missing 'n') and "Interger" (extra 'r') The description states: "This chart shows the complexity of different algorithms when sorting one million integers (from 1 to 1000).". However it is not clear where these numbers come from. Are they comparison counts? Are they swap (or assignment) counts? A combination of both of these measures? What was the initial ordering of the data? Over how many runs were these numbers averaged? How is it that so many of the algorithms all have exactly 1.99316x10^7 as the count? What does "Sorting networks" mean in this picture, and how is the result for it able to not be a whole number? How was bogosort measured given the ridiculously high number shown?
I believe that in its current form, this image adds no value to the article and should be removed. If the information is to be explained and kept then it should converted to a textual form instead.
Malcolm 118.92.109.220 (talk) 04:45, 13 June 2010 (UTC)
This sentence makes no sense to me: "Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly." I can't fix it because I don't know what it's trying to say. So I'm inviting others to work on this. If no fix is forthcoming, I will likely delete this sentence.
By the way, it might be helpful in the summary of each algorithm to describe its performance on various types of datasets (e.g., random, nearly sorted, reversed, few unique elements). MichaelBluejay (talk) 12:56, 22 June 2010 (UTC)
--- How about " ...) which require input data to be in sorted lists."
Your suggestion about how sorts handle pathological cases is a good one, but I suspect it can quickly degrade into confusion. For instance, performance of quicksort on pre-structured data will depend a lot on how the pivot is chosen, and this decision is up to the implementer, and not really part of the quicksort definition. Many implementations have 'tweaks' to protect against pathological cases.
184.147.234.114 (talk) 02:27, 10 February 2013 (UTC)
Consider this sorting network as included in the Sorting network article. Let's put [2, 1a, 1b, 0] on the wires with 'a' and 'b' as markers for the initial order without them belonging to the sorting key. If this sorting network is stable, we can expect it to return [0, 1a, 1b, 2]. The way I see it, it just doesn't:
2, 1a, 1b, 0 is the initial configuration.
1b, 1a, 2, 0 results from the first comparison. 2 > 1, thus we swap.
1b, 0, 2, 1a results from the second comparison. 1 > 0, thus we swap.
0, 1b, 1a, 2 results from the next two comparisons. We swap both since 1 > 0 and 2 > 1.
0, 1b, 1a, 2 is the result. No swap in the last comparison since 1 = 1.
However, [0, 1b, 1a, 2] does not equal [0, 1a, 1b, 2], which was our expected result. From this counterexample follows that sorting networks are not stable sorts in the general case.
So… am I missing anything here? —Preceding unsigned comment added by 129.13.72.197 (talk) 11:23, 23 June 2010 (UTC)
Agreed - there may be a subclass of networks which are stable, but I've not found any discussion of this; I've looked at various example diagrams and have found it easy to find counter-examples in each. Stability would almost certainly come at a cost in extra levels (and more expensive than just 'tagging' the values to force stability). Table entry "Yes" is either plain wrong, or misleading. 184.147.234.114 (talk) 02:05, 10 February 2013 (UTC)
Quantum sorting is not faster than normal sorting (http://arxiv.org/abs/quant-ph/0102078) but might offer better time-space tradeoffs. Thus, Quantum sort does not need to have its own article. I propose merging the brief content from quantum sort into the sorting algorithm article. Comments? Please also comment on the quantum sort talk page so that we can delete that article and incorporate it into this one. --DFRussia (talk) 20:56, 29 June 2010 (UTC)
The section Bubble sort claims:
Looks like false to me. Because of the code brevity of the algorithm, it instead should be heavily used on pretty short lists in naive Q&D implementations where a sort is needed. Also it is often combined with quicksort and quickersort for when the to-be-sorted sublists are under a certain length, such as 3 or 4 elements. This use to improve the sorting speed. So the statement is dubious. Rursus dixit. (mbork3!) 19:57, 6 July 2010 (UTC)
I don't think that's true. If quick & dirty is required, one can implement Quicksort in a single line as in [1]. For sorting of short sub-lists, I have observed variants on Insertion sort much more often than Bubble sort. For the case of finite lengths on those sub-lists, optimal compare-and-swap sequences are known for lists with a maximum length of at least 47 items, probably more. I think there's even a sequence on Sloane's for that, can't seem to find it right now. —Preceding unsigned comment added by 129.13.72.197 (talk) 16:17, 10 July 2010 (UTC)
Is this sorting demo page an external link that should or should not be included in the article. Baltar, Gaius (talk) 05:06, 6 January 2011 (UTC)
Discussion on this sorting algorithm page and its inclusion in the external links section.
I have undone the addition of this link because, IMO, it is blatant self promotion. Furthermore, I and at least one other editor report problems with the animations there crashing or hanging for substantial periods of time. Reyk YO! 06:48, 10 October 2010 (UTC)
Seeing as this section was already there
I believe these links are appropriate for WP because currently there is not enough diversity in the existing examples. You have one that constrains a viewer to a having the JRE installed, and another is non-interactive through the use of animated GIFs. From this StackOverflow question I found this sorting demo page.
The sorting demo is built on open standards, using HTML5's canvas (with support for IE) and JavaScript to display an interactive animated sort. This demo is compatible with almost all browsers and operating systems, including support for mobile devices such as Apple's iPhone, iPod, iPad and other mobile devices (namely Android based). Open standards allow for community improvement and investigation, rather then simply seeing a few bars move you can download the source and research it yourself. While I will concede that this is less of an issue in sort algorithms that have publicly implementations, it is a good path to follow and more conducive to student learning purposes.
In regards to the hanging a user's browser I find no issue with it. If you do then I'm sure contacting the author with more specific details will yield a fix. As far as denigrating the use of Internet Explorer, the most offensive statement I could find is as follows:
: IE users will notice a overall sluggishness due to IE not implementing native <canvas> support. You have my sympathies.
Internet Explorer does not have native canvas support, and the author supports this browser through the use of a excanvas plugin that will reduce the speed at which the animation can be displayed.
Baltar, Gaius (talk) 20:17, 2 December 2010 (UTC)
Suggesting that a user support standards compliant browsers is reasonable, and the fact that extra effort seems to be made to support Internet Explorer should be noted. The Author states Some sorts (bubble) are particularly intensive and not recommended for older / slower computers., not that will cause browsers to go to lunch for a while. There is a momentary stall considering the large amount of pre-computation required to smoothly render the bubble sort. Considering the source (JavaScript) one can assume that the browsers with faster JavaScript engines will perform better, this is not bias but rather pertinent information.
The argument that other demos have gaps means this one should not isn't valid. This demo is filling gaps left by others, and as such plays a vital role in offering the most options to users. Suggesting that this is beta software is incorrect. Baltar, Gaius (talk) 14:56, 6 December 2010 (UTC)
Continuing. If there are not more opposed I would like inclusion of this link. Baltar, Gaius (talk) 14:56, 6 December 2010 (UTC)
What other links to animations are there? All I see is http://www.sorting-algorithms.com/. Ztothefifth (talk) 18:50, 23 December 2010 (UTC)
Another possible link is http://sortvis.org/. Ztothefifth (talk) 21:06, 23 December 2010 (UTC)
Attempting Consensus Can we concede that this page offers a interactive sort visualization that is not tied to any platform or operating system requirements, promoting open standards, and has minor stability problems on few platforms? If we can, I believe that inclusion is supported. Baltar, Gaius (talk) 15:18, 4 January 2011 (UTC)
Strong Support These arguments are ridiculous; if you run IE, you should not expect anything to work IMO. But jokes aside, this is a great visualization of sorting algorithms that can help the reader understand the differences. In many cases, and especially so with our CS articles, the articles are too technical (for the average reader), involving runtime complexity, which data structures the algorithms are best implemented in, etc. As a Computer Scientist, I understand these are invaluable to the article. However, they are not "newbie friendly" at all. This provides a great top-level introductory view of sorting algorithms. Also, W/R/T to the larger demos taking longer to pre-process, I think that is a fine and normal limitation. To be honest, I'm surprised that such a trivial "inconvenience" perhaps really outweighs the benefit of deeper understanding of algorithms. Sheesh. jheiv talk contribs
Glrx I would like to come to a consensus with you before adding the link back in. I would ask that you list any remaining objections to inclusion. This has been dragged on long enough. Baltar, Gaius (talk) 18:43, 7 January 2011 (UTC)
Oppose crashed or stalled IE8. This is supposed to be an encyclopedia not a soapbox for some pinhead to tell me what software to run on my computer. If you think it is such a brilliant demo turn it into a gif and have done with it.Greglocock (talk) 04:27, 11 January 2011 (UTC)
I think bubble sort is stable (in contrary to what that written in the table) —Preceding unsigned comment added by 79.177.127.22 (talk) 09:55, 2 November 2010 (UTC)
When it says n*log(n) what is the base of the log function? Is it binary (2), decimal (10), natural (e), or some other base? —Preceding unsigned comment added by 69.91.165.139 (talk) 20:04, 15 November 2010 (UTC)
I came looking for assistance in manually sorting tens of thousands of random Election Ballots into a hundred geographic (Precinct) districts. Similarly the Postal Services machine-sort millions of pieces of mail into millions of buckets (zipcodes, routes and addresses). Carrier personnel manually direct-sort their mail into an array of "pigeon-holes" before delivery distribution.
Unfortunately all emphasis here is towards electronic Data-processing. I've got to give these lots of thought to determine applicability to physical-sorts, using physical motions, requiring real-time, and limited buckets within reach or operator constraints. Does EDP sort-theory apply, or have lessons for large physical sorts?
Are info or comments about best physical-sort algorithms appropriate here? What differences apply due to human or mechanical vs electronic/cyber media and speeds? HalFonts (talk) 07:20, 19 November 2010 (UTC)
The best case for TimSort should be O(n). It is not just a hybrid mergesort but a hybrid natural mergesort. If the data contains runs that are ordered or reverse ordered or a mixture, then it is between O(n) and O(n * log n). See http://bugs.python.org/file4451/timsort.txt
The same can be said for SmoothSort. If the runs are ordered (but not reverse ordered), then it is O(n). The best cases on these should reflect this. Stephen Howe (talk) 22:39, 25 November 2010 (UTC)
What's happened to this section? Just two curly brackets at the moment. Sam Dutton (talk) 14:01, 26 November 2010 (UTC)
How does it have two different averages? —Tamfang (talk) 07:43, 15 December 2010 (UTC)
Because it is an open problem as to what the asymptotic behaviour of shell sort is. Different gap sequences have different asymptotic behaviour. I will see if better bounds can be found as I believe recent publications by computer theorists have managed to give tighter bounds for shell sort.
Stephen Howe (talk) 21:25, 20 December 2010 (UTC)
In the table of comparisons, shouldn't Shell sort be categorized as "Exchanging and Insertion"? It's more of a hybrid of both than just insertion. — Preceding unsigned comment added by 67.183.10.109 (talk) 19:15, 27 August 2017 (UTC)
I dont think this is true, it is only true for quicksort for linked lists. It is not how the pivot is handled, as the article describes, but the fact that all equal elements within the partition set must retain their original order while partitioning. To do so, requires a stable partition (function in C++ library). stable partition requires auxilary memory and cant be done in O(N) without the memory. Any comments?
Stephen Howe (talk) 21:46, 10 December 2010 (UTC)
Thank you. I have seen. But there is nothing on this page that talks about stable partitioning for quicksort. In any case, I think I would have heard something of it. In the past 20 years, Bentley & McIlroy's groundbreaking "Engineering a Sort function" in 1993 introduced 3-way partitioning (sometimes known as "fat pivot") for Quicksort which has also been investigated by Sedgewick See "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf" "http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf" which are downloadable PDF's. In terms of partitioning, 2-way partitioning is a maximum of N/2 swaps, for 3-way partitioning (Dutch National Flag problem), it can be as little as ((5 * N) / 9) swaps. But in both cases, neither are stable. It is not pivot element that matters, it is the fact that large blocks of multiple duplicates still retain there original order. I have yet to see stable partioning can be done in O(N) swaps with no auxilary memory. Therefore I motion this reverts to quicksort not being stable unless someone posts URLs to white papers that indicate that recent research indicate that Quicksort can be made stable. NOTE: Quicksort for linked lists can be stable, but I am talking about the array version which I believe this Wiki article addresses.
Stephen Howe (talk) 22:37, 12 December 2010 (UTC)
Is a kind of un-algorithm. It simply triangulates from what data is so far sorted (discouraged / takes extra time). But implemented (see code) it shows shows some surprising benefits. Is sometimes referred to being "a sort in which data becomes available for streaming rapidly" (and formidable multi-field). Some books refer to such a method but I haven't seen it one of them code it or compare it's benefits. Interesting for just that. Enjoy. User:Sven nestle2/Perfect Sort / Triangulating Sort
Excuse me Glrx did you have time to see my corrections yet?
I am trying to provide a good topic. Please say if there is any reason to hold it back.
Wikipedia:Identifying reliable sources. "~ the reliability of a source depends on context. Each source must be carefully weighed to judge ~" I don't see other sorts showing publisher. Wikipedia:No original research. "~ that includes any analysis or synthesis of published material that serves to advance a position not advanced by the sources ~". I'm sure I didn't make any unfounded conclusions. Triangulation - very basic stuff.
But that's parsing hairs. The original post was bad and I'm not sure if you've looked at the new post.
I haven't tried to read the code at User:Sven nestle2/Perfect Sort / Triangulating Sort, but from the verbal description it seems that you're merely giving an exotic name to multikey comparison (if x.key1==y.key1 then compare x.key2 with y.key2, and so on) which can be incorporated into any sort algo. —Tamfang (talk) 18:53, 13 June 2011 (UTC)
Mr. Tamfang thank you. As to removal of past edits yes I was trying to keep my talk section small but I see your point. I'm sorry if my article is not easily instructive I try to make it clear soon. I note you are not Glrx who I asked and have no response from.
As to your multi-key comment you are somewhat right: what you listed would work in one dimension (but yields no new index in one dimension). However it would not work in two and higher dimensions as some way of indexing must be found. It must specify AND track traversal some way. Many sorts do this with assumed partitions to specify and recursion to track. Recursion invisibly "stores" traversal indexing but with poor efficiency. It is amazing that "Triangulation Sort" keeps up near highest speeds and can beat other sorts at a few things isn't it? Recursion wastes but also looses order (you cannot output until all records are finished with such methods) (also: debugging an unusual orders can be frustrating). A sort cannot waste indexing time and still have it. Triangulations sort's best features are not "raw time" - as stated above and on it's page.
If however you believe sorting two and higher dimensions is not a problem and requires no indexes please say how :) I'd love to hear it. Also I do not see a reference for "multi key comparison" algorithm. Is there one other than "triangulation sort"?
— Preceding unsigned comment added by 68.227.219.57 (talk) 20:45, 14 June 2011 (UTC)
Who said all data must be one dimensional? Do not believe this person. — Preceding unsigned comment added by 68.227.219.57 (talk) 16:08, 17 June 2011 (UTC)
The overview says library sort was first published in 2004, but the library sort page says 2006. Which is correct? John lindgren (talk) 13:49, 10 June 2011 (UTC)
I found the general algorithm for spaghetti sort, as well as linking articles. — Preceding unsigned comment added by Ahshabazz (talk • contribs) 00:11, 27 June 2011 (UTC)
I just removed Spaghettisort from the list, because by the wikipedia article that describes it, it is not a real sorting algorithm. Spaghetti sort requiers that a "massively parallel CPU system" needs to be able to find the longest spaghetti in o(1) time, in order for this to work, but without describing that part of the sorting algorithm, the description is incomplete. There is no such thing as an o(1) sorting algorithm, so the precondition that makes "Spaghetti sort" able to exist as an algorithm, does not exist. In other words "Spaghetti sort algorithm" is not a Computer Science algorithm, but a method with spaghetti, that would require a sorting algorithm on a computer, which is not related to spaghetti. Dybdahl (talk) 06:25, 7 July 2011 (UTC)
I agree with removing it from this article, but note that the requirement is O(1), not o(1). Finding the largest strand in time O(1) is impractical, requiring custom purpose parallel hardware scaling with problem size; finding it in o(1) is impossible. CRGreathouse (t | c) 03:50, 7 October 2011 (UTC)
A question - spaghetti sort as currently listed claims O(n^2) memory, but its article claims O(n) memory, which seems far more intuitive to me as each value is only tracked once (on its own processor). Is there a reason for this difference? — Preceding unsigned comment added by 12.184.104.214 (talk) 04:57, 21 December 2012 (UTC)
I find this sorting algorithm to be amusing:
http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort — Preceding unsigned comment added by 174.137.113.43 (talk) 00:50, 20 July 2011 (UTC)
This should be included as a non-comparison sort, as there isn't anything there that compares to the slow comparison sort.. 'slow sort' at the moment.--31.185.238.2 (talk) 00:38, 12 March 2012 (UTC)
that... you could add in the table if an algorithm is online or not. http://en.wikipedia.org/wiki/Category:Online_sorts Mdtr (talk) 03:26, 3 August 2011 (UTC)
I would appreciate a clarification, either on this page or the logarithms page, of what is meant by . KlappCK (talk) 15:00, 30 August 2011 (UTC)
According to the definition given at the start of the article, duplicates-removing sorting is not sorting. But that kind of algorithms exist; some languages/run-time systems have built-in sort functions with the possibility to specify whether it is needed to remove the duplicates at the same time while sorting, or to preserve them.
One example: pigeonhole sort with removal of duplicates is essentially what the array-based sieve of Eratosthenes is doing while collecting ⁄ marking the composites, and list-based variant exists which performs duplicates-removing mergesort.
Where and how can this be addressed? Or is it already, somewhere? Any pointers, anyone? Thanks. WillNess (talk) 08:20, 22 September 2011 (UTC)
Duplicate-removing sorts can be done in 2-steps: 1. The sort is done 2. An extra pass is made comparing an element with the next element. If the next element is identical on the key, then it should be overwritten by the next successive element. So for identical elements, the first element is preserved. Stephen Howe (talk) 21:31, 28 January 2012 (UTC)
A I just published a new sorting algorithm I worked on for the last 18+ months. I think Over-sort is past "worthy of notice", and into ground breaking territory, but I'm probably biased. — Preceding unsigned comment added by 84.229.4.103 (talk) 08:24, 14 October 2011 (UTC)
Standard Template Library includes a stable_sort() function, but does not define how it is implemented. In the case of Microsoft's Visual Studio, stable_sort() uses a temp vector (1/2 the size of the data to be sorted), and is not an in-place merge sort. It uses insertion sort to create chunks of 32 elements, then merges chunks until chunk size equals vector size. The sort algorithms section should not include a reference to Standard Template Library as an example of an in place merge sort. A specific implementation of STL's stable_sort() might use an in-place merge sort, but stable_sort() is not defined that way. Rcgldr (talk) 02:06, 9 December 2011 (UTC)
The ISO C++ standard (1998 and now 2011) does give implementation constraints on how stable_sort should be implemented. It says "Complexity: It does at most N log2(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N)." It works out that 3 STL algorithms are adaptive: inplace_merge(), stable_partition(), stable_sort(). They are allowed to acquire a temporary buffer and if the memory is available, then the minimum complexity is achieved. If the memory is not available but a smaller amount is available, then the algorithm degrades gracefully in the direction of the maximum complexity. In the case of Visual Studio, it uses a hybrid merge sort where the initial step is various insertion sorts before merging the results back and forth to the temporary buffer. For VS2003, VS2005, VS2008 the temporary buffer is the size of all the elements. For VS2010, the temporary buffer is 0.5 the size of all the elements as the well-known trick of merge-sorting 2 halves and then merging one half in the temporary buffer with the other remaining half is employed. This cuts down the overhead. Any algorithm that meets the complexity and stability requirements of ISO C++ can be used but most STLs use a hybrid adaptive mergesort. Stephen Howe (talk) 22:02, 28 January 2012 (UTC)
Before you start the sorting of the N given elements you should check if the given elements already have the desired sort order (check if (a[i-1] <= a[i]) for all i=(1, .. N-1)). This additional check operation has only a linear run time complexity O(N). That means if the given array is already sorted (this is always the best case) so the run time complexity is always O(N). This additional check operation can be executed at the begin of each sort algorithm. That means in particular that each sort algorithm in the best case always has a linear run time complexity O(N).
Aragorn321 (talk) 05:54, 19 July 2012 (UTC)
Currently, this column has only red (n^2 or worse) and green (better than n^2). Should nlog(n) be made yellow, for consistency's sake? 140.247.41.147 (talk) 13:48, 23 July 2012 (UTC)
This "page maker" is deleting or mis-representing code for faster sort algorithms. Never stating where they came from or sources. Giving confusing explinations for advanced algorthms and leaving out practical issues such as found in unix sort(1) (ie, stability, tape v. memory, caching). Deleting sumbitted old and new algorthims (ie, mine but others). But has publishes "timsort" which is a joke algorithm. Say he has a tester and all algorithms but has no evidence of having the same. And the sources cited have 0 to do with the origion books and creators of the algorithms.
August 31, 2012
To whom it may concern (at Wikipedia),
Back in the late 1970's I read about two sorting algorithms that are not mentioned at all in this "Sorting algorithm" article. They are Quickersort and Quickestsort. At that time: Quickersort was the latest published improvement of Quicksort; and Quickestsort was the fastest sorting method possible theoretically and (its algorithm was) a trade secret of the U.S.A. Federal Government. If anyone knows more (history) about this, please add it to this "Sorting algorithm" article. Quicksort and Quickersort were written about in the book: "Sorting and Sort Systems" by Harold Lorin, ISBN 0-201-14453-0, Copyright © 1975 by Addison-Wesley Publishing Company, Inc., part of "The Systems Programming Series" [book #4 of 4]. I don't remember where I read about Quickestsort. I thought it was in that book, but it is not listed in the index.
Sincerely yours,
JPD 22:15, 31 August 2012 (UTC)
$ echo "Wikibooks Wikipedia Wiktionary" | sort --random-sort Wikipedia Wikibooks Wiktionary
The sort in GNU/free Linux uses merge sorting which is explained in the Sorting algorithm wiki page.
Sort uses merge sorting and is speedy to complete 1 column sorting (in a table of rows and colums of words to be selected and sorted).
There is a new sort(1), headsort(1), using an algorthim with opposite speed properties of merge sort that when sorting more than one column can finish in 1/2 the time, or when only needing to begin streaming the sorted data can finish in 1/2 the time (thus head), and can fork sorting jobs better (though neither does by default): but more often looses to sort's merge when sorting 1 column: it has opposite benefits of merge. Streaming and columns headsort(1) can being streaming in less than 1/2 the time. It's used when use columns and piping data are more often than not used.
If you are interested in headsort(1) "1/2 the time" contact johnandsara2@cox.net or sven_nestle2 on wiki with subject "sort algorithm".
It's good to note that for top speed no algorithm is needed just memory: however quite impractically allot is need for any appreciable task especial where used for random tasks; such a thing is useable only within a single program.
Euclid sort sorts in O(N*log(N)) time n needs O(1) mem first we got two groups of sorted items to b merged lets try to describe backward possible variant: first we c what is the last item (in reverse order) from the second group that remains at its place second we c where is moving up the first contestant , in reverse order, by following in reverse order, the elements of first group third we c how many elements from the second group will come compactly with the contestant that i mentioned fourth we apply some Euclid arange function to put the elements in the rite place when exit the loop we probabily will have at least an Euclid arange (as much, but no more) to get the array sorting done
idd wish credits if the case Florin Matei, Romania 93.118.212.93 (talk) 07:36, 22 February 2013 (UTC)
ok no problem, suit urself abt that policy of urs i dont think its wrong or anything i was just trying make a decent buck, noone i know likes to publish my ideas, like i said im a poor encoder also thow i got a few ideas, u might b ceen my ip page thank u... n im not playing the smartes nor the poorest here: i just feel like found a way to speak abt my creativity. Florin 93.118.212.93 (talk) 15:36, 27 February 2013 (UTC)
its all abt merging two sorted groups: main repeated action is to move same number of elements from group first n group second (group interchange same no of elements) so we'll have all the elements of groups (sorted in the future) but not in place, then well repeat starting with the group of less length 4 not charging that much the stack... as a strategy we can alternate between remained smaller group n the bigger 1:1 alternate that assure O(log(n)) stack with some strategy against hazard. when memorize parameters of a group in the stack , memorize also the "breaking point" also
93.118.212.93 (talk) 08:28, 4 March 2013 (UTC)
This sort only works on a sequential set of numbers in some random permutation, using swaps to sort the set of numbers. The worst case number of swaps is n-1. Example code for when the set of number is {0, 1, ..., n-1} stored in an array a[]:
void sort(void)
{
int i;
for(i = 0; i < n; i++)
while( a[i] != a[a[i]])
swap(a[i], a[a[i]]);
}
Several
Rcgldr (talk) 09:18, 27 April 2013 (UTC)
// A is an array of size n
A[] = ... ;
// generate array of indexes I
for(i = 0; i < n; i++)
I[i] = i;
// sort I based on values in A
sort(I, A);
// sort A using the sorted list of indexes in I
// while also sorting I
for(i = 0; i < n; i++){
while( I[i] != I[I[i]] ){
swap(A[I[i]], A[I[I[i]]]);
swap( I[i], I[I[i]] );
}
}
Rcgldr (talk) 01:04, 29 April 2013 (UTC)
special_cycle_sort
in B. K. Haddon, "Cycle-Sort: A Linear Sorting Method", The Computer Journal, 1990. —Ruud 17:16, 29 April 2013 (UTC)There should be a section explaining what an in place sort is just like there is a section for explaining stability of sorting — Preceding unsigned comment added by Nileshrathi01 (talk • contribs) 14:07, 5 October 2013 (UTC)
From my university studies I recall there being something called the 0-1 principle. The statement is something like this: "If an oblivious comparison-based sorting algorithm correctly sorts data consisting of only 0s and 1s, then it correctly sorts any data."
I forget the exact wording, but the idea of it is that, if an algorithm meeting certain criteria works as a sorting algorithm for arrays/lists containing only two distinct values, then it works as a sorting algorithm for lists whose elements are taken from an arbitrarily large totally-ordered set.
Does anybody know anything about this? The search hits I've found are explicitly about sorting networks, but what I was taught referred to sorting algorithms more generally. Obviously not all 0-1 sorting algorithms are general sorting algorithms - counting sort with only two counters is an obvious counter-example (pardon the pun). But what are the "certain criteria"? Something that can be said about most sorting algorithms is
But the aforementioned counting sort can be adapted to meet these criteria, so they are clearly not sufficient.
It may be the case that it is only a theorem for sorting networks, and my lecturer just intended us to use it as a heuristic test to see if a sorting algorithm seems correct. Still, can anyone provide any further insight into this, such that we might be able to add something to the article about it? — Smjg (talk) 17:42, 30 November 2013 (UTC)
For what it's worth, I've just tried searching again and found this: [2]
What is important, however, is whether the algorithm has any conditional behaviour, other than just the swapping of the elements, based on the result of the comparison.
Maybe "oblivious comparison-exchange" was the phrasing my lecturer used. I guess that this phrase means an operation of the form "if A > B, swap A and B", and the essence is that the data is in a black box and the algorithm has access to it only by this operation (which returns no value, hence "oblivious") plus knowledge of the length of the array.
This means that, for a given algorithm and input size, the sequence of oblivious comparison-exchanges is a constant. So what we really have is an algorithm for building a sorting network and then applying it. That said, on a given pair A and B, it can equally be either "if A > B, swap A and B" or "if B > A, swap B and A". So if you don't consider sorting networks to be allowed to have reverse comparators, then we have a generalisation of the sorting network 0-1 principle to a wider class of algorithms. Otherwise, it doesn't really generalise the principle at all.
Maybe what we can still say is that the 0-1 principle can be used to prove the correctness of some sorting algorithms. I'll see what I can come up with.... — Smjg (talk) 14:52, 12 April 2014 (UTC)
"Sorting networks" aren't a singular algorithm that can be described as a single best/worst/average case for time and memory, but they're listed as such in the chart. They're also listed in a special category for sorts that are incredibly impractical or require special hardware. That may be true for the AKS sorting network it's apparently referring to, but small and efficient sorting networks are actually a lot faster than insertion sort, even though insertion sort is credited as being the fastest. In my experience they're anywhere from 2 to 5 times faster than insertion sort.
What should be done about this? My recommendation is to remove sorting networks from the chart entirely and only refer to them as a concept that can be applied to many sorting algorithms (AKS, even-odd, bitonic, bubble and insertion, etc.), either to construct hardware or to make an algorithm for fixed-size data sets. — Preceding unsigned comment added by BonzaiThePenguin (talk • contribs) 03:40, 11 April 2014 (UTC)
I'd like to see an explanation of the terms used in the Method column of the Comparison Sorts table in the Comparison of Algorithms section: Partitioning, Merging, Selection, Insertion, Exchanging, Distribution, Random Shuffling. These don't seem to be explained until later in the article, if at all. I think a short paragraph or illustration describing these methods is warranted.2620:36:8000:10:95B8:2D6C:17C9:12AB (talk) 16:59, 17 September 2014 (UTC)
If "Quicksort for linked lists" has different characteristics than "Quicksort for arrays" -- one is stable, and the other is not -- then they are different enough for this article to list them as two separate algorithms. Stephen Howe suggested they were different in #Quicksort can be stable?.
Is there a more reliable source that mentions "Quicksort for linked lists" than "Stable Quicksort With Linked List" or "Optimal Quicksort for Single Linked List" ? — Preceding unsigned comment added by DavidCary (talk • contribs) 22:36, 21 August 2015
Is there a more reliable source that mentions "Quicksort for linked lists" than Yes. [1] I believe it covers "Quicksort for linked lists". I have a copy, I will check. Stephen Howe (talk) 00:44, 14 December 2016 (UTC)
References
Big-O should denote upper bounds, and Big-Omega denotes lower bounds. I realize that at least colloquially, people don't pay that much attention and say Big-O in all cases, often intending a meaning closer to that of Big-Theta (the conjunction of Big-O and Big-Omega), but that is incorrect usage and should be corrected on Wikipedia, or am I missing a semi-formal convention which standardizes that usage? At the very least the article on Big-O notation seems to agree with me at a quick glance.
"A fundamental limit of comparison sorting algorithms is that they require linearithmic time – O(n log n) – in the worst case"
"Comparison-based sorting algorithms (...) need at least O(n log n) comparisons for most inputs."
"These are all comparison sorts, and so cannot perform better than O(n log n) in the average or worst case."
Syrak (talk) 22:49, 16 November 2015 (UTC)
O(f(n)) denotes the set of all g(n) such that there exist positive constants C and n0 with |g(n)| ≤ Cf(n) for all n ≥ n0. Ω(f(n)) denotes the set of all g(n) such that there exist positive constants C and n0 with |g(n)| ≥ Cf(n) for all n ≥ n0 - Knuth, D. E. (1976). Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2), 18-24. |
The best worst case. The first problem that arises naturally is to find comparison trees that minimize the maximum number of comparisons made. (Later we shall consider the average number of comparisons.) Let S(n) be the minimum number of comparisons that will suffice to sort n elements. If all the internal nodes of a comparison tree are at levels < k, it is obvious that there can be at most 2k external nodes in the tree. Hence, letting k = S(n), we have . Stirling's approximation tells us that , hence roughly comparisons are needed.
|
-Esquivalience t 02:05, 6 March 2016 (UTC)The number of comparisons required by a comparison sorting algorithm is roughly n log n comparisons in the worst case (some algorithms require proportionately n log n comparisons);[1] in better cases, it is possible to perform comparison sorting in at most a multiple of n comparisons.[2]
References
((cite book))
: Invalid |ref=harv
(help)hello and thank you for reading about this "not paper book published" interesting sort algo.
http://sourceforge.net/projects/headsort/
This isn't on the main page or book but i beleive DOES matter. Simply because it was never tried in publications doesn't mean it doesn't matter; results matter, and are in forma gnu sort(1) for trial.
Mergesort is stable and fast, it heuristicly "bins" like radix and speedily compares LINES of data using strcmp - making MULTI-DIMENSIONAL sorting (multi field) very fast. extra fields (dimensions) are (smartly) catenated onto previous ones (gnu sort does this) and never compared if strcmp stops before then.
However - Mergesort heuristic failure is comparing item that have ALREADY been compared.
Traditionally it is thought a "triangulation sort" cannot be fast because it needs two or thee dimensions to compare characters (also no cpu strcmp to use). However it gains by never comparing two things twice. That still lags behind merge sort best case, but does win in some cases.
"hsort" or headsort can win in a few major ways.
ONE: when the first bin is done (which is triangulated and cannot finish sooner), headsort program can begin piping sorted output. (unlike a simple "sift up" sort, it can finish the tail quickly as well). this is important if anyone is waiting to view data or has a battery that cannot withstand needless background heat while they view.
TWO: "hsort" found two NEW improvements which may well make it a good algo to use in general. First instead of data[line][field][characters] it tried data[field][line][characters] and nearly being deleted attempt: found a special case which allowed a dimension reduction of 1, at moderate cost (a good improvement). Doing so ate up all time to try the other...
THREE: Next and recently, HSORT tried a simpler dimensional reduction. Using a 1d array sorted that output ptr to 3d array. Impossible per say: but distribution counting allows it on the tail, so it is fully 1/2 true.
FOUR: the old adage *foo[][][] is expesive is not as true as it had been in the 8086 days. New CPU can do some extra dimensions in 1 CPU tick, which remove more of the remaining handicap of the 'hsort' algorithm in practice.
With those two (or fee) dimensional reductions my tests show that hsort beats "merge sort" used in gnu sort heavily in best cases, and also still wins in headsort's worst cases: just all around faster FOR multi dimensional sorting.
I'd like others comments but I'm well aware its' rare any proffessors exchange comments on algorithms.
hsort is debuggable (unlike recursive heuristics, it's flow is mostly natural)
hsort also has implications in distributive computing because it can recurse dimensions and doesn't require merging or waiting per say (implementation of piping finished bins in 123 order aside which is easy, which is always true single process)
Allowing an sssumption this hsort is faster in a worthy manner, it does matter in that scientific algorithms can finish or never finish. Many math algorithms have sorting at their core (for example, factoring). While for "web server technology" sorting might not be important - it is important whether scientific processes can finish and show a result. And that is simply re-iterating a textbook big-O-notation explanation.
LASTLY. hsort algorithm is not an idea it's available for use (has other algo in a collection too) as a gnu-sort compatible program, and has a demo "mini sort" prog to make it's portability and use more clear.
— Preceding unsigned comment added by 72.219.207.23 (talk) 23:16, 19 March 2016 (UTC)
The image that shows whether a sort is stable or not (Sorting_stability_playing_cards) correctly shows the output of an unstable sort. The example of a stable sort can really only be said to not be shown to be unstable. If the description indicated that it would consistently (or provably) work in that way, it would be better. Dcrafti (talk) 03:59, 17 January 2017 (UTC) Dcrafti
The section "Comparison of algorithms" gives n2 as the average time complexity of comb sort. I am not competent enough to suggest what the correct complexity is (I suspect that this is a rather sophisticated problem with a result of something like nsome number between 1 and 2), but n2 cannot be right; in practice this algorithm sorts huge lists at speeds comparable to nlogn algorithms. Same about worst case actually. — Preceding unsigned comment added by 2001:7D0:8891:1380:BC17:C2C1:9181:5154 (talk) 07:53, 7 August 2017 (UTC)
Shell sort is clearly not a variant of bubble sort. Why is it listed under the headline "bubble sort and variants"? Dp99 (talk) 09:34, 6 June 2018 (UTC)
The "Twin Sort Technique" (https://arxiv.org/abs/1710.07992) is the latest core computer sorting algorithm and got published recently, and I am the main author of it. Can this be covered and added to your portal (https://en.wikipedia.org/wiki/Sorting_algorithm)? Millions of students, researchers and engineers get benefited out of this addition.
VeereshDevireddy (talk) 15:10, 16 August 2018 (UTC)
It occurs to me that caching effects on modern (or not so modern) processors can greatly affect the speed of some memory access patterns, and that could be significant in some sort algorithm comparisons. Not knowing where else to mention it, though it might be useful in pages for specific sort algorithms, I am starting here. Gah4 (talk) 20:43, 4 September 2019 (UTC)
The dynamic web page in the second paragraph implies (at least to me) a Publicly accessible web page, whose content runs afoul of FERPA.
The second paragraph of the Stability section starts with:
Stability is important for the following reason: say, if the data is sorted first by student name, in some cases, dynamically on the webpage, and now the data is again sorted by which class section they are in.
A webpage containing student name and corresponding class section data would at first glance appear to be "'directory information" but is actually an education record. Therefore if the web page is accessible by others than those with a defined, institutional, education purpose, the web page would be in violation of FERPA.
My feeling is those learning these topics should not be creating things, that, if used with real-life data, would be in violation of the law.
"What is an education record? | Protecting Student Privacy". studentprivacy.ed.gov. US Department of Education. Archived from the original on Christmas 2018. Retrieved 26 February 2020 – via https://studentprivacy.ed.gov/frequently-asked-questions.[...]records include but are not limited to grades, transcripts, class lists, student course schedules, health records (at the K-12 level), student financial information (at the post secondary level), and student discipline files. [...]((cite web))
: Check date values in:|archive-date=
(help); External link in(help)
|via=
"FERPA Tutorial - Directory Information|When is Directory Information Not Really Directory Information?". Office of The University Registrar - Penn State. Retrieved 26 February 2020.It is important to also understand the concept of "implicit disclosure." An implicit disclosure may occur when a list consists only of directory information but the list itself by definition reveals non-directory information. For example, a list of names and email addresses of all students who have a particular grade-point average reveals the students' GPAs. Likewise, a class list containing names and email addresses of the students reveals class enrollments. Since neither grade-point average nor class enrollment are directory items, releasing these lists without prior consent of the students constitutes a FERPA violation.((cite web))
: CS1 maint: url-status (link)
--Lent (talk) 08:55, 26 February 2020 (UTC)
Row | City | State Code |
Old → New Row |
City | State Code |
Original → Initial Sorting → Following stable sort |
City | State Code
|
---|---|---|---|---|---|---|---|---|
1 | Chicago | IL | 13 → 1 | Rockford | IA | 13 → 1 → 1 | Rockford | IA |
2 | Rockford | IL | 2 → 2 | Rockford | IL | 4 → 5 → 2 | Champaign | IL |
3 | Evanston | IL | 3 → 3 | Evanston | IL | 1 → 4 → 3 | Chicago | IL |
4 | Champaign | IL | 1 → 4 | Chicago | IL | 3 → 3 → 4 | Evanston | IL |
5 | Detroit | MI | 4 → 5 | Champaign | IL | 2 → 2 → 5 | Rockford | IL |
6 | New York | NY | 12 → 6 | Rockford | MI | 5 → 7 → 6 | Detroit | MI |
7 | Buffalo | NY | 5 → 7 | Detroit | MI | 12 → 6 → 7 | Rockford | MI |
8 | Milwaukee | WI | 15 → 8 | Rockford | MN | 15 → 8 → 8 | Rockford | MN |
9 | Albany | NY | 11 → 9 | Syracuse | NY | 9 → 12 → 9 | Albany | NY |
10 | Green Bay | WI | 6 → 10 | New York | NY | 7 → 11 → 10 | Buffalo | NY |
11 | Syracuse | NY | 7 → 11 | Buffalo | NY | 6 → 10 → 11 | New York | NY |
12 | Rockford | MI | 9 → 12 | Albany | NY | 11 → 9 → 12 | Syracuse | NY |
13 | Rockford | IA | 14 → 13 | Rockford | TN | 14 → 13 → 13 | Rockford | TN |
14 | Rockford | TN | 8 → 14 | Milwaukee | WI | 10 → 15 → 14 | Green Bay | WI |
15 | Rockford | MN | 10 → 15 | Green Bay | WI | 8 → 14 → 15 | Milwaukee | WI |
Row | City | State Code |
Old → New Row |
City | State Code |
Original → Initial Sorting → Following stable sort |
City | State Code
| ||
---|---|---|---|---|---|---|---|---|---|---|
1 | Chicago | IL | 13 → 1 | Rockford | IA | 13 → 1 → 1 | Rockford | IA | ||
2 | Rockford | IL | 2 → 2 | Rockford | IL | 4 → 5 → 2 | Champaign | IL | ||
3 | Evanston | IL | 3 → 3 | Evanston | IL | 1 → 4 → 3 | Chicago | IL | ||
4 | Champaign | IL | 1 → 4 | Chicago | IL | 3 → 3 → 4 | Evanston | IL | ||
5 | Detroit | MI | 4 → 5 | Champaign | IL | 2 → 2 → 5 | Rockford | IL | ||
6 | New York | NY | 12 → 6 | Rockford | MI | 5 → 7 → 6 | Detroit | MI | ||
7 | Buffalo | NY | 5 → 7 | Detroit | MI | 12 → 6 → 7 | Rockford | MI | ||
8 | Milwaukee | WI | 15 → 8 | Rockford | MN | 15 → 8 → 8 | Rockford | MN | ||
9 | Albany | NY | 11 → 9 | Syracuse | NY | 9 → 12 → 9 | Albany | NY | ||
10 | Green Bay | WI | 6 → 10 | New York | NY | 7 → 11 → 10 | Buffalo | NY | ||
11 | Syracuse | NY | 7 → 11 | Buffalo | NY | 6 → 10 → 11 | New York | NY | ||
12 | Rockford | MI | 9 → 12 | Albany | NY | 11 → 9 → 12 | Syracuse | NY | ||
13 | Rockford | IA | 14 → 13 | Rockford | TN | 14 → 13 → 13 | Rockford | TN | ||
14 | Rockford | TN | 8 → 14 | Milwaukee | WI | 10 → 15 → 14 | Green Bay | WI | ||
15 | Rockford | MN | 10 → 15 | Green Bay | WI | 8 → 14 → 15 | Milwaukee | WI |
City | State |
---|---|
Chicago | IL |
Rockford | IL |
Evanston | IL |
Champaign | IL |
Detroit | MI |
New York | NY |
Buffalo | NY |
Milwaukee | WI |
Albany | NY |
Green Bay | WI |
Syracuse | NY |
Rockford | MI |
Rockford | IA |
Rockford | TN |
Rockford | MN |
City | States |
---|---|
Albany | NY |
Buffalo | NY |
Champaign | IL |
Chicago | IL |
Detroit | MI |
Evanston | IL |
Green Bay | WI |
Milwaukee | WI |
New York | NY |
Rockford | MI |
Rockford | IA |
Rockford | TN |
Rockford | MN |
Rockford | IL |
Syracuse | NY |
City | States |
---|---|
Rockford | IA |
Rockford | IL |
Evanston | IL |
Chicago | IL |
Champaign | IL |
Rockford | MI |
Detroit | MI |
Rockford | MN |
Syracuse | NY |
New York | NY |
Buffalo | NY |
Albany | NY |
Rockford | TN |
Milwaukee | WI |
Green Bay | WI |
City | States |
---|---|
Rockford | IA |
Champaign | IL |
Chicago | IL |
Evanston | IL |
Rockford | IL |
Detroit | MI |
Rockford | MI |
Rockford | MN |
Albany | NY |
Buffalo | NY |
New York | NY |
Syracuse | NY |
Rockford | TN |
Green Bay | WI |
Milwaukee | WI |
City | States |
---|---|
Albany | NY |
Buffalo | NY |
Champaign | IL |
Chicago | IL |
Detroit | MI |
Evanston | IL |
Green Bay | WI |
Milwaukee | WI |
New York | NY |
Rockford | IA |
Rockford | IL |
Rockford | MI |
Rockford | MN |
Rockford | TN |
Syracuse | NY |
Derived from Jeffery S. Leon's Sorting Algorithms — Stability". [1]
To sort by the above tables, click on the triangle. Then hold the Shift key and click on the triangle to sort by another column, while keeping the order for the first column when values of the second column are equal.
I need some advice on MOS Table Summaries, Table Color (used to emphasize motion of rows during sorting), and the five across tables.
Also the mobile Wikipedia seems to expand the tables by default, with no obvious way to hide the table.
Also which, if any data elements, should I get rid of? I think omitting a few more cities named Rockford might help, right?
Anyway, I would like this to be a nice example, which allows interaction using the built-in Wikipedia functionality for sortable tables.
Finally, where can I find documentation for normal users that the holding Shift key while clicking a sort triangle maintains the previous column(s) sort order? Did you know about this?
--Lent (talk) 06:13, 28 February 2020 (UTC)
Our sorting software might allow sorting on only one field at a time. We may 1) First sort the array A alphabetically by city. 2) Then sort the array A alphabetically by state, using a stable sorting algorithm.
I would like to discuss a revert done by an anonymous IP. The reason for the revert was that the expected runtime is given in the average case. This is, however, wrong. The expected runtime is different from the average case. These two names are different concepts: the average case is a description of the input. The input meaning here the list to sort. We assume some distribution of the input and calculate the expectation for the runtime over this distrubtion. This is different for "expected runtime". The 'expected' in 'expected runtime' does not relate to the input, but instead to what we often call 'random bits'. The 'random bits' are not part of the input (this would make the whole concept of probablistic programming ad absurdum). Therefore we can not say that the average-case is identical to the expected runtime. We have infinitely many expected runtimes, especially we have a worst-case expected runtime, a best-case expected runtime and again we also have an average-case expected runtime.
Even worse, saying that the worst-case runtime of bogosort is infinite is at best misleading. That is because there is really no concept in which infinite would be a meaningful runtime for bogosort. I would accept using the phrase 'certainly unbounded', meaning assuming that there is no randomess, the runtime is not bounded by any function depening on the input. Even saying that the runtime is unbounded (without using the word certainly) is misleading as the probability for unbounded runtime is 0 and even the expected runtime is at most n x !n. I would therefore ask to redo my change to fit more with the given source (which uses the same semantics) and with the current research. --PhoenixIra (talk) 17:25, 22 June 2020 (UTC)
An introductory sentence says, "For optimum efficiency, the input data should be stored in a data structure which allows random access rather than one that allows only sequential access."
But that is true only when the cost of random access is very small. If the volume of input data is too long to fit in available fast memory (e.g., RAM), then having input data stored in a data structure residing on slow memory (e.g., hard disk, or magnetic tape) then such a data structure can be terrible.
I'm changing the introductory sentence to say, "For optimum efficiency, input data in fast memory should be stored in a data structure which allows random access rather than one that allows only sequential access." DavidForthoffer (talk) 20:41, 4 February 2021 (UTC)
First bullet in 'Classification'
Computational complexity (worst, average and best behavior) in terms of the size of the list (n). For typical serial sorting algorithms, good behavior is O(n log n), with parallel sort in O(log2 n), and bad behavior is O(n2)
Does anyone know what the 'O' for bad behaviour for parallel sorting is?
Darcourse (talk) 10:12, 22 July 2021 (UTC)
Link: https://en.wikipedia.org/wiki/Timsort — Preceding unsigned comment added by 2001:16b8:1e5b:ba00:2c00:cbff:fe64:7ae (talk • contribs)
I was surprised to find no page on wikipedia for comparing online sorting algorithms, and no section in the Online algorithm page. I'm not sure if it deserves its own page, a section in this page with a new comparison table, or maybe a column in an existing comparison table? Privychick (talk) 13:32, 18 March 2022 (UTC)
What is the point of the tk screenshot at the top?? —Tamfang (talk) 00:46, 21 April 2023 (UTC)
Just wondered if AI sorts should be added:
GrahamHardy (talk) 16:42, 23 June 2023 (UTC)
1 strength of ArrayV is, that the numbers, which are visualized as bars, are always integers, as I have never seen pigeonhole sort failing to sort an array.
There are some wrong time complexities in Sorting algorithm#Others.
Simple pancake sort should be O(n) best and O(n2) average and worst and Bitonic sorter should be O(n log2n), best average and worst, where log2n means (log n)2. Well, these time complexities fit well to the results in https://www.youtube.com/watch?v=8MsTNqK3o_w&t=2825s andhttps://www.youtube.com/watch?v=v4Uo0Pi6odo&t=15s. The fastest a sorting algorithm can reach is O(n). In array v oof 2, sb broke ArrayV by running parallel bitonic sort with 16384 numbers, but I think, it was just a freeze bug, like https://www.youtube.com/watch?v=vlLrmCifVRY&t=1646s.
Another strength of ArrayV is how the sorting algorithms are visualized. AceOfSpadesProduc100 himself said in (follow-up video) Threaded pattern-defeating merge sort on ArrayV-v4.0, in Parallel bitonic sort on ArrayV, in Parallel odd-even merge sort on ArrayV and in ArrayV-v4.0's parallel sorting algorithms, that he uses an Intel Core i7-9750H, which has 6 cores and 12 threads. But, the way ArrayV visualizes the sorting algorithms lets the parallel sorting algorithms do the fully parallel method. For example, parallel bitonic sort could use flan sort rotations. 94.31.83.138 (talk) 19:43, 23 August 2023 (UTC)
bold = correction
part 2: https://www.youtube.com/watch?v=wqibJMG42Ik
patience sort: O(n) best, O(n log n) average and worst, O(n) memory, stable
tournament sort: O(n log n) best, average and worst, O(n) memory, stable
bitonic sort: O(n log^2 n) best, average and worst, O(1) memory, unstable
odd-even merge sort: O(n log^2 n) best, average and worst, O(1) memory, unstable
pairwise sorting network: O(n log^2 n) best, average and worst, O(1) memory, unstable
stooge sort: O(n^2.71) best average and worst, O(1) memory, unstable
slow sort: O(n^(log n)) best average and worst, O(1) memory, unstable
variants and hybrids: https://www.youtube.com/watch?v=FntVy6lPVyo
cartesian tree sort: O(n log n) best, average and worst, O(n) memory, stable
Stalin sort: O(n) best, average and worst, O(1) memory, stable
sleep sort: O(n) best, O(n + r) average and worst, O(n) memory, stable
miracle sort: O(n) best (on a sorted list), O(inf) average and worst, O(1) memory, stable
power sort: O(n * n!) best, average and worst, O(n * n!) memory, stable
A sorting algorithm can not be faster than O(n).
Stalin sort increases unsorted values to the largest previously read value (https://www.youtube.com/watch?v=hyOlWQ9MLPI). For example, [1, 2, 5, 3, 6, 4, 10] becomes [1, 2, 5, 5, 6, 6, 10].
Sleep sort is a time-based sorting algorithm. The smallest number wakes up first and the largest number wakes up last (https://www.youtube.com/watch?v=ktgxMtWMflU&t=210s). Equal numbers will wake up at the same time, but waking up is swapless.
Miracle sort only makes comparisons and power sort prints all the permutations in auxiliary arrays, so both of them are swapless.
Swaps of non-adjacent numbers are what makes a sorting algorithm unstable (https://www.youtube.com/watch?v=KJuxI1BBLyQ&t=403s).
some examples
cycle sort, bitonic sort, odd-even merge sort, pairwise sorting network, stooge sort and slow sort: Swap non-adjacent numbers. = unstable
insertion sort and binary insertion sort: Swap only adjacent numbers. = stable
patience sort, tournament sort, cartesian tree sort, Stalin sort, sleep sort, miracle sort and power sort: no swaps = stable 94.31.89.138 (talk) 20:28, 28 October 2023 (UTC)