주판 정렬

주판 정렬 또는 비드 소트(bead sort), 중력 정렬, 그래비티 소트(gravity sort)는 내추럴 정렬 알고리즘이다. 2002년 Joshua J. Arulanandham, Cristian S. Calude, Michael J. Dinneen이 개발하였고 이론컴퓨터과학유럽협회게시판(The Bulletin of the European Association for Theoretical Computer Science)에 출판되었다. 주판 정렬의 디지털 및 아날로그 하드웨어 구현체들 모두 O(n)의 정렬 시간을 달성할 수 있지만 이 알고리즘의 구현체는 소프트웨어에서는 상당히 더 느린 경향이 있으며 자연수의 정렬 목록에 대해서만 사용할 수 있다. 또, 최상의 조건에서도 이 알고리즘은 O(n²)의 공간이 필요하다.

구현체

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

외부 링크

• “Bead-Sort: A Natural Sorting Algorithm” (PDF). 2017년 8월 9일에 원본 문서 (PDF)에서 보존된 문서. 2005년 1월 1일에 확인함.  (114 KiB)
• Bead Sort in MGS, a visualization of a bead sort implemented in the MGS programming language
• Bead Sort on MathWorld
• Bead Sort interactive visualization