KEMBAR78
Lecture 22 Radix Sort | PDF | Computer Programming | Applied Mathematics
Scribd
Upload
38 views9 pages

Lecture 22 Radix Sort

This document provides an overview of Radix Sort, including its advantages over traditional sorting algorithms and its complexity analysis. It explains the process of sorting names and numbers using Radix Sort, detailing the multiple passes required based on the number of digits. Additionally, it discusses the complexity in different cases, highlighting scenarios where the number of passes is significantly less than the number of elements.

Uploaded by

ranahassanirfan2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
38 views9 pages

Lecture 22 Radix Sort

This document provides an overview of Radix Sort, including its advantages over traditional sorting algorithms and its complexity analysis. It explains the process of sorting names and numbers using Radix Sort, detailing the multiple passes required based on the number of digits. Additionally, it discusses the complexity in different cases, highlighting scenarios where the number of passes is significantly less than the number of elements.

Uploaded by

ranahassanirfan2005
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

Radix Sort

CS 250 Data Structures and Algorithms


Prof. Dr. Faisal Shafait

1/9
Sorting

Learning Objectives

In this lecture you will learn the


Understanding of different sorting algorithms based on their
running-time complexities
Understanding of the use of Radix Sort and its advantage over
other sorting algorithms
Complexity analysis of Radix Sort

2/9
Sorting

Sorting: running-time

Traditional O (n 2 ) sorting algorithms:


Bubble sort
Selection sort
Insertion sort
Faster Ê(nln(n)) sorting algorithms:
Heap sort
Quick sort
Merge sort
Linear-time sorting algorithms:
Counting sort
Radix sort

3/9
Sorting

Radix sort

Commonly used to sort names


Sort the names with respect to their first letter.
use counting sort with 26 bins (for 26 letters), where 26 is called the
Radix.
After the first pass, the names are sorted w.r.t the first letter. The
first bin will contain all names starting with the letter A (e.g.
Ahmad, Abubakar, Ayesha, Abiha)
Perform a second pass within each bin based on the second letter.
The names in the first bin would be sorted w.r.t. two letters (e.g.
Abubakar, Abiha, Ahmad, Ayesha)
After k passes, the names will be sorted, where k is the length of
the longest name.

4/9
Sorting

Radix sort: Example

Consider sorting this array with Radix Sort


348, 143, 361, 423, 538, 128, 321, 543, 366
Radix = 10, so we need 10 bins
Each number has 3 digits, so k = 3 passes needed to sort the array
First Pass: sort w.r.t. the least significant digit

5/9
Sorting

Counting sort: Example – Pass 2

Second Pass: Take the result of the first pass (collect values
column-wise) and sort w.r.t. the middle digit

6/9
Sorting

Counting sort: Example – Pass 3

Third Pass: Take the result of the second pass (collect values
column-wise) and sort w.r.t. the most significant digit

7/9
Sorting

Radix sort – Complexity analysis

There are k passes, in each which we iterate through all n elements,


hence the complexity is O (kn)

Case 1: k does not depend on n and k << n


Example: Data containing age (in years) of the whole world’s
population, i.e. n > 7 Billion; k = 3
Complexity will be Ê(n)

Case 2: k depends on n
Example: Data containing ID card numbers of the whole population
of Pakistan, i.e. n ∼ 200 Million; k ∼ log10 (n)
Complexity will be O (n logd (n)), where d is the Radix

8/9
Sorting

Reading Material

For further reading, please refer to


https://www.programiz.com/dsa/radix-sort
https://www.cs.usfca.edu/galles/visualization/RadixSort.html

9/9

You might also like