“Радикс Сорт Python” Ответ

Радикс Сорт Python

def radixSort(inputArray, base = None):
    """Sort elements by powers using buckets to store lists based on integer columns"""    
    if base is None:
      base = 10  ## For decimals
    
    ## Check for the non negative number as this method is only applicable for non negative numbers
    assert len({i <= 0 for i in inputArray}) == 1, 'Non negative numbers in the list'
        
    n = 0
    max_digit = len(str(max(inputArray)))  # find max number and get length of digits 
    

    while max_digit > n:
        bucket = [[] for _ in range(10)]        # create buckets (2D array), 10 is used as we are using decimal and distinct value of last digit is 10
        for i in inputArray:
            bucket[i//(base**n)%10].append(i)   # put corrensponding numbers in bucket
        index = 0
        for i in range(len(bucket)):       # loop through bucket
            
            stage_two = bucket[i]          # find lists of numbers in bucket
            for nums in stage_two:
                inputArray[index] = nums     # add sorted list back into original list
                index += 1
        n += 1     # increasing the power of n

    return inputArray
  
## Terst Case
assert radixSort([170, 45, 75, 90, 2, 802, 2, 66]) == [2, 2, 45, 66, 75, 90, 170, 802], "The radix sort failed"
Jeevan Shrestha

Radix Sort в Python

# Radix sort in Python


# Using counting sort to sort the elements in the basis of significant places
def countingSort(array, place):
    size = len(array)
    output = [0] * size
    count = [0] * 10

    # Calculate count of elements
    for i in range(0, size):
        index = array[i] // place
        count[index % 10] += 1

    # Calculate cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Place the elements in sorted order
    i = size - 1
    while i >= 0:
        index = array[i] // place
        output[count[index % 10] - 1] = array[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(0, size):
        array[i] = output[i]


# Main function to implement radix sort
def radixSort(array):
    # Get maximum element
    max_element = max(array)

    # Apply counting sort to sort elements based on place value.
    place = 1
    while max_element // place > 0:
        countingSort(array, place)
        place *= 10


data = [121, 432, 564, 23, 1, 45, 788]
radixSort(data)
print(data)
Xerothermic Xenomorph

Радикс Сорт Python

def countingSortForRadix(inputArray, placeValue):
    # We can assume that the number of digits used to represent
    # all numbers on the placeValue position is not grater than 10
    countArray = [0] * 10
    inputSize = len(inputArray)

    # placeElement is the value of the current place value
    # of the current element, e.g. if the current element is
    # 123, and the place value is 10, the placeElement is
    # equal to 2
    for i in range(inputSize): 
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] += 1

    for i in range(1, 10):
        countArray[i] += countArray[i-1]

    # Reconstructing the output array
    outputArray = [0] * inputSize
    i = inputSize - 1
    while i >= 0:
        currentEl = inputArray[i]
        placeElement = (inputArray[i] // placeValue) % 10
        countArray[placeElement] -= 1
        newPosition = countArray[placeElement]
        outputArray[newPosition] = currentEl
        i -= 1
        
    return outputArray

def radixSort(inputArray):
    # Step 1 -> Find the maximum element in the input array
    maxEl = max(inputArray)

    # Step 2 -> Find the number of digits in the `max` element
    D = 1
    while maxEl > 0:
        maxEl /= 10
        D += 1
    
    # Step 3 -> Initialize the place value to the least significant place
    placeVal = 1

    # Step 4
    outputArray = inputArray
    while D > 0:
        outputArray = countingSortForRadix(outputArray, placeVal)
        placeVal *= 10  
        D -= 1

    return outputArray
    
input = [2,20,61,997,1,619]
print(input)
sorted = radixSort(input)
print(sorted)
Xerothermic Xenomorph

Ответы похожие на “Радикс Сорт Python”

Вопросы похожие на “Радикс Сорт Python”

Больше похожих ответов на “Радикс Сорт Python” по Python

Смотреть популярные ответы по языку

Смотреть другие языки программирования

Shell/Bash
C#
C++
C
CSS
HTML
Java
JavaScript
Objective-C
PHP
Python
Sql
Swift
Ruby
TypeScript
Go
Kotlin
Assembly
R
VBA
Scala
Rust
Dart
Elixir
Clojure
Haskell
Matlab
Erlang
Cobol
Fortran
Scheme
Perl
Groovy
Lua
Julia
Delphi
Abap
Lisp
Prolog
Pascal
ActionScript
Basic
Solidity
PowerShell
GDScript
Excel