You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 44.201.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 23:54, 31 July 2024.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪AntiCompositeNumber‬. The reason given is Open proxy/Webhost: Visit the FAQ if you are affected .
- Start of block: 13:55, 18 August 2022
- Expiry of block: 13:55, 18 April 2025
Your current IP address is 44.201.28.123. The blocked range is 44.201.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((Multiple issues|((refimprove|date=October 2017))((notability|date=October 2017))))
'''Bead sort''', also called '''gravity sort''', is a [[natural computing|natural]] [[sorting algorithm]], developed by [[Joshua J. Arulanandham]], [[Cristian S. Calude]] and [[Michael J. Dinneen]] in 2002, and published in ''The Bulletin of the [[European Association for Theoretical Computer Science]]''.<ref name=Arulanandham2002>((cite web |last1=Arulanandham |first1=Joshua J. |last2=Calude |first2=Cristian S. |last3=Dinneen |first3=Michael J. |date=January 2002 |title=Bead-Sort: A Natural Sorting Algorithm |publisher=Department of Computer Science, University of Auckland |url=https://researchspace.auckland.ac.nz/bitstream/handle/2292/3679/171joshua.pdf |access-date=2021-05-14))</ref>  Both [[Digital data|digital]] and [[analog computer|analog]] hardware [[implementation]]s of bead sort can achieve a sorting time of ''[[Big O Notation|O]]''(''n''); however, the implementation of this algorithm tends to be significantly slower in [[software]] and can only be used to sort lists of [[positive integer]]s.  Also, it would seem that even in the best case, the algorithm requires ''[[Big O Notation|O]]''(''n<sup>2</sup>'') space.

==Algorithm overview==
[[File:BeadSort-Figure1.svg|thumb|right|Step 1: Suspended beads on vertical poles.]]
[[File:BeadSort-Figure2.svg|thumb|right|Step 2: The beads have been allowed to fall.]]
The bead sort operation can be compared to the manner in which beads slide on parallel poles, such as on an [[abacus]].  However, each pole may have a distinct number of beads.  Initially, it may be helpful to imagine the beads suspended on vertical poles.  In Step 1, such an arrangement is displayed using ''n=5'' rows of beads on ''m=4'' vertical poles.  The numbers to the right of each row indicate the number that the row in question represents; rows 1 and 2 are representing the positive integer 3 (because they each contain three beads) while the top row represents the positive integer 2 (as it only contains two beads).<ref name="rowconventions" group=notes>By convention, a row representing the positive integer ''k'' should have beads on poles 1..''k'' and poles ''k''+1..''m'' should be empty.  This is not a strict requirement, but will most likely simplify implementation.</ref>

If we then allow the beads to fall, the rows now represent the same integers in sorted order.  Row 1 contains the largest number in the set, while row ''n'' contains the smallest.  If the above-mentioned convention of rows containing a series of beads on poles 1..''k'' and leaving poles ''k''+1..''m'' empty has been followed, it will continue to be the case here.

The action of allowing the beads to "fall" in our physical example has allowed the larger values from the higher rows to propagate to the lower rows.  If the value represented by row ''a'' is smaller than the value contained in row ''a+1'', some of the beads from row ''a+1'' will fall into row ''a''; this is certain to happen, as row ''a'' does not contain beads in those positions to stop the beads from row ''a+1'' from falling.

The mechanism underlying bead sort is similar to that behind [[counting sort]]; the number of beads on each pole corresponds to the number of elements with value equal or greater than the index of that pole.

==Complexity==

Bead sort can be implemented with four general levels of complexity, among others:
*''[[Big O Notation|O]]''(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice.
*''[[Big O Notation|O]]''(<math>\sqrt{n}</math>): In a realistic physical model that uses gravity, the time it takes to let the beads fall is proportional to the square root of the maximum height, which is proportional to n.
*''[[Big O Notation|O]]''(n): The beads are moved one row at a time.  This is the case used in the analog and [[digital hardware]] solutions.
*''[[Big O Notation|O]]''(S), where S is the sum of the integers in the input set: Each bead is moved individually.  This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations.

Like the [[Pigeonhole sort]], bead sort is unusual in that in worst case it can perform faster than ''[[Big O Notation|O]]''(''n'' [[logarithm|log]] ''n''), the fastest performance possible for a [[comparison sort]] in worst case. This is possible because the key for a bead sort is always a positive integer and bead sort exploits its structure.

== Implementation ==
This implementation is written in [[Python (programming language)|Python]]; it is assumed that the ((code|input_list)) will be a sequence of integers. The function returns a new list rather than mutating the one passed in, but it can be trivially modified to operate in place efficiently.
<syntaxhighlight lang="python3">
def beadsort(input_list):
    """Bead sort."""
    return_list = []
    # Initialize a 'transposed list' to contain as many elements as
    # the maximum value of the input -- in effect, taking the 'tallest'
    # column of input beads and laying it out flat
    transposed_list = [0] * max(input_list)
    for num in input_list:
        # For each element (each 'column of beads') of the input list,
        # 'lay the beads flat' by incrementing as many elements of the
        # transposed list as the column is tall.
        # These will accumulate atop previous additions.
        transposed_list[:num] = [n + 1 for n in transposed_list[:num]]
    # We've now dropped the beads. To de-transpose, we count the
    # 'bottommost row' of dropped beads, then mimic removing this
    # row by subtracting 1 from each 'column' of the transposed list.
    # When a column does not reach high enough for the current row,
    # its value in transposed_list will be <= 0.
    for i in range(len(input_list)):
        # Counting values > i is how we tell how many beads are in the
        # current 'bottommost row'. Note that Python's bools can be
        # evaluated as integers; True == 1 and False == 0.
        return_list.append(sum(n > i for n in transposed_list))
    # The resulting list is sorted in descending order
    return return_list
</syntaxhighlight>

We can also implement the algorithm using [[Java (programming language)|Java]].<ref>((cite web |url=https://www.geeksforgeeks.org/bead-sort-natural-sorting-algorithm/|title=Bead Sort - A Natural Sorting Algorithm |last=Nigam |first=Palash
| publisher=GeeksForGeeks))</ref>

<syntaxhighlight lang=java>
    public static void beadSort(int[] a)
    {
        // Find the maximum element
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
 
        // allocating memory
        int[][] beads = new int[a.length][max];
 
        // mark the beads
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i]; j++) {
                beads[i][j] = 1;
            }
        }
 
        // move down the beads
        for (int j = 0; j < max; j++) {
            int sum = 0;
            for (int i = 0; i < a.length; i++) {
                sum += beads[i][j];
                beads[i][j] = 0;
            }
 
            for (int i = a.length - 1; i >= a.length - sum;
                 i--) {
                a[i] = j + 1;
            }
        }
    }
</syntaxhighlight>

==Notes==
((Reflist|group=notes))

==References==
<references/>

==External links==
*((cite web |title=Bead-Sort: A Natural Sorting Algorithm |access-date= 2005-01-01 |url= https://www.cs.auckland.ac.nz/%7Ejaru003/research/publications/journals/beadsort.pdf |archive-url= https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/%7Ejaru003/research/publications/journals/beadsort.pdf |archive-date= 2017-08-09 |url-status= dead ))&nbsp;((small|(114&nbsp;[[Kibibyte|KiB]])))
*[http://mgs.spatial-computing.org/ImageGallery/EXEMPLES/BeadSort/index.html Bead Sort in MGS], a visualization of a bead sort implemented in the [http://mgs.spatial-computing.org MGS] programming language
*[http://mathworld.wolfram.com/Bead-Sort.html Bead Sort on MathWorld]
*[http://www.kaufer.org/BeadSort/ Bead Sort interactive visualization]

((sorting))

[[Category:Sorting algorithms]]
[[Category:2002 in computing]]

Pages transcluded onto the current version of this page (help):

Bead sort (edit)
Template:Ambox (view source) (template editor protected)
Template:Cite web (view source) (protected)
Template:Code (view source) (template editor protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Hlist/styles.css (view source) (protected)
Template:Main other (view source) (protected)
Template:More citations needed (view source) (template editor protected)
Template:Multiple issues (view source) (template editor protected)
Template:Multiple issues/styles.css (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Notability (view source) (template editor protected)
Template:Refimprove (view source) (template editor protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:Small (view source) (protected)
Template:Sorting (edit)
Template:Strong (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:String (view source) (protected)
Module:Unsubst (view source) (protected)
Module:Yesno (view source) (protected)

Return to Bead sort.

Retrieved from "https://en.wikipedia.org/wiki/Bead_sort"