CS-251 – Design and Analysis of Algorithms

Instructor: Dr. Zuhair Zafar

Lecture # 14: Radix Sort

1
Types of Sorting Algorithms
• Non-recursive/Incremental comparison sorting
• Selection sort
• Bubble sort
• Insertion sort
• Recursive comparison sorting
• Merge sort
• Quick sort
• Heap sort
• Non-comparison linear sorting
• Counting sort
• Radix sort
2
• Bucket sort
Radix Sort
• The lower bound for the comparison-based sorting algorithm is
Ω(𝑛 log 𝑛) such as, merge sort, quick sort, heap sort.

• Counting sort can’t be used if a range of key-value is large (suppose

range is 1 to n2)

• Radix sort is efficient than the comparison sorting algorithm until

the number of digits (key) is less than log 𝑛.

• Radix sort uses counting sort as its sub-routine to sort elements of

every digit.

3
Working of Radix Sort
• In radix sort, we first sort the elements based on the last digit (least
significant digit).

• Then the result is again sorted by the second digit.

• Continue this process for all digits until we reach the most
significant digit.

4
Example

5
Example

6
Example

7
Example

8
Example

9
Example

10
Example

11
Example

12
Example

13
Example

14
Example

15
Example

16
Example

17
Example

18
Example

19
Example

20
Example

21
Example

22
Example

23
Example

24
Example

25
Example

26
Example

27
Example

28
Example

29
Example

30
Example

31
Example

32
Example

33
Example

34
Example

35
Example

36
Example

37
Example

38
Example

39
Example

40
Example

41
Example

42
Example

43
Example

44
Example

45
Example

46
Example

47
Example

48
Example

49
Example

50
Example

51
Example

52
Example

53
Example

54
Example

55
Example

56
Example

57
Example

58
Example

59
Example

60
Example

61
Example

62
Example

63
Example

64
Example

65
Example

66
Example

67
Example

68
Example

69
Example

70
Example

71
Example

72
Example

73
Example

74
Example

75
Example

76
Example

77
Example

78
Example

79
Example

80
Example

81
Example

82
Example

83
Example

84
Example

85
Example

86
Example

87
Example

88
Example

89
Example

90
Example

91
Example

92
Example

93
Example

94
Example

95
Example

96
Example

97
Example

98
Example

99
Example

100
Example

101
Pseudocode of Radix Sort
𝑹𝒂𝒅𝒊𝒙 − 𝑺𝒐𝒓𝒕(𝑨, 𝒅)
//𝐼𝑡 𝑤𝑜𝑟𝑘𝑠 𝑠𝑎𝑚𝑒 𝑎𝑠 𝑐𝑜𝑢𝑛𝑡𝑖𝑛𝑔 𝑠𝑜𝑟𝑡 𝑓𝑜𝑟 𝑑 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑝𝑎𝑠𝑠𝑒𝑠.
//𝐸𝑎𝑐ℎ 𝑘𝑒𝑦 𝑖𝑛 𝐴[1. . 𝑛] 𝑖𝑠 𝑎 𝑑 − 𝑑𝑖𝑔𝑖𝑡 𝑖𝑛𝑡𝑒𝑔𝑒𝑟.
//(𝐷𝑖𝑔𝑖𝑡𝑠 𝑎𝑟𝑒 𝑛𝑢𝑚𝑏𝑒𝑟𝑒𝑑 1 𝑡𝑜 𝑑 𝑓𝑟𝑜𝑚 𝑟𝑖𝑔ℎ𝑡 𝑡𝑜 𝑙𝑒𝑓𝑡. )
𝒇𝒐𝒓 𝒋 = 𝟏 𝒕𝒐 𝒅 𝒅𝒐
//𝐴[] − − 𝐼𝑛𝑖𝑡𝑖𝑎𝑙 𝐴𝑟𝑟𝑎𝑦 𝑡𝑜 𝑆𝑜𝑟𝑡
𝒇𝒐𝒓 𝒊 = 𝟎 𝒕𝒐 𝟗
𝑪[𝒊] = 𝟎
//𝑆𝑡𝑜𝑟𝑒 𝑡ℎ𝑒 𝑐𝑜𝑢𝑛𝑡 𝑜𝑓 "keys" 𝑖𝑛 𝑐𝑜𝑢𝑛𝑡[]
//𝑘𝑒𝑦 − 𝑖𝑡 𝑖𝑠 𝑛𝑢𝑚𝑏𝑒𝑟 𝑎𝑡 𝑑𝑖𝑔𝑖𝑡 𝑝𝑙𝑎𝑐𝑒 𝑗
𝒇𝒐𝒓 𝒊 = 𝟎 𝒕𝒐 𝒏 − 𝟏 𝒅𝒐
𝑪 𝒌𝒆𝒚 𝒐𝒇 𝑨 𝒊 𝒊𝒏 𝒑𝒂𝒔𝒔 𝒋 = 𝑪 𝒌𝒆𝒚 𝒐𝒇 𝑨 𝒊 𝒊𝒏 𝒑𝒂𝒔𝒔 𝒋 + 𝟏
𝒇𝒐𝒓 𝒌 = 𝟏 𝒕𝒐 𝟏𝟎 𝒅𝒐
𝑪[𝒌] = 𝑪[𝒌] + 𝑪[𝒌 − 𝟏]
//𝑏𝑢𝑖𝑙𝑑 𝑡ℎ𝑒 𝑟𝑒𝑠𝑢𝑙𝑡𝑖𝑛𝑔 𝑎𝑟𝑟𝑎𝑦 𝐵 𝑏𝑦 𝑐ℎ𝑒𝑐𝑘𝑖𝑛𝑔
//𝑛𝑒𝑤 𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴[𝑖] 𝑓𝑟𝑜𝑚 𝐶[𝑘]
𝒇𝒐𝒓 𝒊 = 𝒏 − 𝟏 𝒅𝒐𝒘𝒏𝒕𝒐 𝟎 𝒅𝒐
𝑩[ 𝒄𝒐𝒖𝒏𝒕[𝒌𝒆𝒚 𝒐𝒇(𝑨[𝒊])] ] = 𝑨[𝒊]
𝑪 𝒌𝒆𝒚 𝒐𝒇 𝑨 𝒊 = 𝑪 𝒌𝒆𝒚 𝒐𝒇 𝑨 𝒊 − 𝟏
//𝑁𝑜𝑤 𝑚𝑎𝑖𝑛 𝑎𝑟𝑟𝑎𝑦 𝐴[] 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠 𝑠𝑜𝑟𝑡𝑒𝑑 𝑛𝑢𝑚𝑏𝑒𝑟𝑠
//𝑎𝑐𝑐𝑜𝑟𝑑𝑖𝑛𝑔 𝑡𝑜 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑑𝑖𝑔𝑖𝑡 𝑝𝑙𝑎𝑐𝑒
𝒇𝒐𝒓 𝒊 = 𝟎 𝒕𝒐 𝒏 − 𝟏 𝒅𝒐
𝑨[𝒊] = 𝑩[𝒊]
𝒆𝒏𝒅 𝒇𝒐𝒓(𝒋)
𝒆𝒏𝒅 𝒇𝒖𝒏𝒄 102
Asymptotic Analysis of Radix Sort
• In the Radix sort algorithm running time depends on the intermediate
sorting algorithm which is counting sort.

• If the range of digits is from 1 to k, then counting sort time complexity is

O(n+k).

• There are d passes i.e counting sort is called d time, so total time
complexity is 𝐎(𝐧𝐝 + 𝐤𝐝) = 𝐎(𝐧𝐝). As 𝐤 = 𝐎(𝐧) and d is constant, so
radix sort runs in linear time.

• Worst Case Time complexity: 𝑂(𝑛𝑑)

Average Case Time complexity: 𝑂(𝑛𝑑)
Best Case Time complexity: 𝑂(𝑛𝑑)
Space Complexity: 𝑂(𝑛 + 𝑘) 103
Sorting In Place: No
Stable: Yes
Radix Sort: Final Comments

• Radix Sort is one of the most efficient and fastest linear sorting
algorithms. It is simple to understand and easy to implement.

• Radix Sort is a good choice for many programs that need a fast
sort.

• Radix Sort can handle larger keys more efficiently as compare to

Counting Sort.

• Radix sort is almost equally efficient as the best comparison-based

sorts (and worse if keys are much longer than log n).
104
Radix Sort: Final Comments
• Why quicksort, or any comparison-based sorting algorithm is more
common than radix-sort?

105
Radix Sort: Final Comments
• Why quicksort, or any comparison-based sorting algorithm is more
common than radix-sort?

1. We can sort arbitrary types using quicksort (i.e., anything that's

comparable), while you are restricted to numbers only with radix
sort. Radix sort just sorts things by their binary representation. It
never compares items against each other.

2. The additional memory requirement (which in it self is a

disadvantage), affects cache performance negatively. All radix
sort implementations use a secondary buffer to store partial 106
sorting results.