Wikipedia:Reference desk/Archives/Computing/2022 May 11

Computing desk
< May 10	<< Apr | May | Jun >>	May 12 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 11

What is the name of this sorting algorithm?

What is the name of this sorting algorithm?

Some joke sorting algorithmn (that I am sure it exist) came into my mind. I am sure this already exist, so I am asking the name of it.

The algorithm:

0-There is a list of numbers A.

1-Create variable minnumber and maxnumber. And list B and list C.

2-Copy values from list A to list B.

3-Look at entire list A to find lowest and biggest number and put them at minnumber and maxnumber.

4-Look at the entire list B and search for numbers equal to maxnumber. Everytime a number is found that fit the rule, put the number at the start at list C and remove from list B this value found.

5-Maxnumber = Maxnumber -1.

6-If Maxnumber >= minnumber go back to 4. If not go to 7.

7-Copy list C to list A.

2804:7F2:5A5:BB11:2922:59C5:1F60:65C5 (talk) 23:38, 11 May 2022 (UTC)

I doubt it has a name. It is a little bit like selection sort but it is a lot worse. Bubba73 ^{You talkin' to me?} 23:59, 11 May 2022 (UTC)

If the numbers from list B keep crowding onto C regardless of the current maxnumber, you'd have the algorithm for boarding an airplane. --Amble (talk) 01:56, 12 May 2022 (UTC)

Bogosort? Mitch Ames (talk) 03:18, 12 May 2022 (UTC)

No, that produces every permutation of the input until it hits a sorted one. Bubba73 ^{You talkin' to me?} 05:10, 12 May 2022 (UTC)

It only works on lists of integers. Its complexity is $O(\infty ),$ which is worse than any thus far named sorting algorithm.  --Lambiam 07:51, 12 May 2022 (UTC)

It is mixture of select sort and count sort, but not very good as a general purpose sorting algorithm.

• You create two additional lists, but need only one.
• You calculate the next value of Maxnumber to look for by reducing the previous value by one. This only works on a list of integers (or elements where the sort key can be represented as an integer) and is inefficient if the range is larger than the number of elements. Sorting the list {1, 65535, 0, 2} will take 65536 iterations. If the range is smaller than the number of elements it's actually quite efficient. Sorting the list {3, 2, 3, 1, 0, 2, 1, 3, 0, 1, 2, 3, 1, 0} will take just 4 iterations of the outer loop, instead of the 14 with a normal select sort. Your algorithm has these properties in common with count sort.
• You propose removing elements from list B when you put them in list C. If the list is implemented as an array data structure, removing an element is a heavy operation. You could also choose to ignore elements larger than Maxnumber. In an in-place algorithm, you would normally swap the element with the element at the target location. On a linked list this isn't a disadvantage; there moving an element from one list to another is more efficient than copy-and-delete.
• Time complexity of your algorithm appears to be $O(n\cdot k)$, with $n$ the number of elements and $k$ the range, which is, on a small range at least, better than select sort ($O(n^{2})$), but worse than count sort ($O(n+k)$), while having the same limitations as count sort. PiusImpavidus (talk) 08:07, 12 May 2022 (UTC)