Radix Sort Algorithm | Integer Sorting | Linear Time Sorting

Introduction

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It is a linear time sorting algorithm that is often used as a subroutine in other sorting algorithms.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/sorting_searching("`Sorting Searching`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/list_comprehensions("`List Comprehensions`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/sorting_searching -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/variables_data_types -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/strings -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/type_conversion -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/conditional_statements -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/for_loops -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/list_comprehensions -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/lists -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/tuples -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/function_definition -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/default_arguments -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/classes_objects -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/encapsulation -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/raising_exceptions -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} python/build_in_functions -.-> lab-268879{{"`Radix Sort: Efficient Integer Sorting Algorithm`"}} end

Radix Sort

Problem

Implement radix sort algorithm to sort a list of integers. The algorithm sorts the integers by comparing their digits starting from the least significant digit to the most significant digit. The algorithm first sorts the integers based on the least significant digit, then the second least significant digit, and so on until the most significant digit is sorted.

Requirements

To implement radix sort, the following requirements must be met:

The input must be a list of integers.
Check for None in place of an array.
Assume array elements are integers.
The digits must be base 10.
The algorithm must be able to handle any number of digits.
The algorithm must fit in memory.

Example Usage

The following are examples of how to use the radix sort algorithm:

None -> Exception
[] -> []
[128, 256, 164, 8, 2, 148, 212, 242, 244] -> [2, 8, 128, 148, 164, 212, 242, 244, 256]

Summary

Radix sort is an efficient algorithm for sorting integers. It sorts the integers by comparing their digits starting from the least significant digit to the most significant digit. The algorithm has a linear time complexity and is often used as a subroutine in other sorting algorithms.

Radix Sort: Efficient Integer Sorting Algorithm