RadixSort: Sorting Larger Integers in Linear Time
"Learn about RadixSort, an algorithm for sorting larger integers in linear time, with detailed explanations, examples, and implementations. Understand the concept of stable sorting and how RadixSort efficiently sorts elements based on their digits. Explore the step-by-step process of RadixSort and its application in sorting arrays of integers with varying digits."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 9: RadixSort
Sorting in Linear Time Algorithm 1. CountingSort This is a stable sort. Example. Definition. A sorting algorithm is stable if it keeps the relative positions for elements of the same value. 0 1 2 3 4 5 6 7 8 9 61 0 41 42 62 31 43 2 32 44 A[0..9] 0 1 2 3 4 5 6 1 0 1 2 4 0 2 C[0..6] Algorithm. CountingSort(A[0..n-1]) 1. for (h=0; h<k; h++) C[h] = 0; for (i=0; i<n; i++) C[A[i]] = C[A[i]] + 1; 2. for (h=1; h<k; h++) C[i] = C[i-1] + C[i]; 3. for (i=n-1; i>=0; i--) C[A[i]] = C[A[i]] 1. B[C[A[i]]] = A[i]; 0 1 2 3 4 5 6 1 0 1 1 2 6 5 4 8 9 8 C[0..6] 0 1 2 3 4 5 6 7 8 9 0 2 31 32 41 42 43 44 61 62 B[0..9] Time = O(n+k) Assume all values in A[0..n-1] are integers between 0 and k-1
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 39 457 720 55 436 657 457 329 720 329 436 39 55 657 39 55 329 436 457 657 720
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits.
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Each stable sort takes time O(n+10) = O(n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Claim: x must be placed before y in the output array by RadixSort. Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Claim: x must be placed before y in the output array by RadixSort. Suppose x = z1 zh-1xh xd, y = z1 zh-1yh yd, where 0 xh < yh 9. Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Claim: x must be placed before y in the output array by RadixSort. Suppose x = z1 zh-1xh xd, y = z1 zh-1yh yd, where 0 xh < yh 9. After the for-loop sorts the hth digit, the array A[n] looks like: Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 x xh y 0 9 yh Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Claim: x must be placed before y in the output array by RadixSort. Suppose x = z1 zh-1xh xd, y = z1 zh-1yh yd, where 0 xh < yh 9. After the for-loop sorts the hth digit, the array A[n] looks like: Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 x xh y 0 9 yh So x is placed before y in the array. Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Example. 329 657 457 39 436 720 55 Theorem. RadixSort outputs a sorted list. 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 Proof. Let x and y be two integers in the input such that x < y. 55 329 436 457 657 720 Claim: x must be placed before y in the output array by RadixSort. Suppose x = z1 zh-1xh xd, y = z1 zh-1yh yd, where 0 xh < yh 9. After the for-loop sorts the hth digit, the array A[n] looks like: Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 x xh y 0 9 yh So x is placed before y in the array. Since all digits of x and y before the hth digit are the same, and since the sorting is stable, x remains before y in the array. Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from left) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 2. Stable sorting is essential. Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from right) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 2. Stable sorting is essential. 3. The elements do not have to be integers. For example, they can be character strings. Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from right) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 2. Stable sorting is essential. 3. The elements do not have to be integers. For example, they can be character strings. 4. It can be generalized to sort integers in [0..n4-1]: Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from right) \\ so 0 k 9 Running time = O(d n)
Sorting in Linear Time Algorithm 1. RadixSort \\ sort larger integers Remarks. 1. When d is a constant, the algorithm is linear time. Example. 329 657 457 39 436 720 55 720 55 436 657 457 329 39 720 329 436 39 55 657 457 39 55 329 436 457 657 720 2. Stable sorting is essential. 3. The elements do not have to be integers. For example, they can be character strings. 4. It can be generalized to sort integers in [0..n4-1]: Hint: each integer r in [0..n4-1] can be written as: R = c3n3 + c2n2 + c1n + c0 or (c3, c2, c1, c0) where 0 ch n - 1 Algorithm. RadixSort(A[n]) \\ elements in array A[n] are integers \\ of at most d digits. for (i = d; i > 0; i--) stably sort \\ e.g., countingsort the array A[n] using the i-th digit (from right) \\ so 0 k 9 Running time = O(d n)
