Linear Sorting
Linear Sorting
Dr Timothy Kimber
March 2018
Introduction
Recalling Comparison Sorts
The running time of these comparison sort algorithms
Mergesort
Heapsort
Quicksort (expected)
are all O(N logN).
Not possible for a comparison sort algorithm to do better
However, there are sorting methods that achieve O(N) performance.
Algorithms (580) Linear Sorting March 2018 2 / 18
Counting Sort Algorithm
Counting Sort
The Counting Sort algorithm sorts integers from a known range
The key operation is to count the occurrences of all values
Counting Sort(Input: A = [A1, . . . ,AN ], k)
For i = 0 to k
C [i ] = 0 <-- one entry per value in the range For j = 1 to N C [A[j ]] = C [A[j ]] + 1 <-- count how many A[j] there are For i = 1 to k C [i ] = C [i ] + C [i − 1] <-- how many less than or equal to i For j = N to 1 B[C [A[j ]]] = A[j ] C [A[j ]] = C [A[j ]]− 1 Return B Algorithms (580) Linear Sorting March 2018 3 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Operation Counting Sort Counts of each value are saved into C Next the counts are accumulated Now C [i ] holds number of values ≤ i Finally copy contents of A to correct positions in B using C Algorithms (580) Linear Sorting March 2018 4 / 18 Counting Sort Performance Counting Sort Time Counting sort makes two passes through the input and two passes through the count table C So, the time taken is ... Counting Sort(Input: A = [A1, . . . ,AN ], k) For i = 0 to k C [i ] = 0 <-- one entry per value in the range For j = 1 to N C [A[j ]] = C [A[j ]] + 1 <-- count how many A[j] there are For i = 1 to k C [i ] = C [i ] + C [i − 1] <-- how many less than or equal to i For j = N to 1 B[C [A[j ]]] = A[j ] C [A[j ]] = C [A[j ]]− 1 Return B Algorithms (580) Linear Sorting March 2018 5 / 18 Counting Sort Performance Properties Counting Sort runs in Θ(N + k) time. Question Under what circumstances does this become O(N) time? Counting Sort is also stable ‘Different’ 3s stay in the same order Can be important when the values are linked to other data This property is used by the next algorithm Algorithms (580) Linear Sorting March 2018 6 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 535 089 158 134 189 158 134 → 189 840 535 558 558 089 840 It makes d passes through the data Each pass sorts on the ith digit only Algorithms (580) Linear Sorting March 2018 7 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 535 158 189 134 840 558 089 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 8 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 840 134 535 158 558 189 089 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 9 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 840 134 535 158 558 189 089 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 10 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 134 535 840 158 558 189 089 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 11 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 134 535 840 158 558 189 089 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 12 / 18 Radix Sort Algorithm Radix Sort Radix Sort is used to sort a set of d-digit values 089 134 158 189 535 558 840 Counter-intuitively, the first sort is on the least significant digit It allows counting sort to be used per digit, over a much smaller range e.g. For decimal numbers there are 10 values to sort on Algorithms (580) Linear Sorting March 2018 13 / 18 Radix Sort Algorithm Radix Sort The algorithm is simple to state Radix Sort(Input: A = [A1, . . . ,AN ], d) For i = 0 to d Use a stable sort to sort A on digit i Counting Sort can implement the stable sort efficiently Algorithms (580) Linear Sorting March 2018 14 / 18 Radix Sort The Radix The Radix Radix Sort(Input: A = [A1, . . . ,AN ], d) For i = 0 to d Use a stable sort to sort A on digit i Discussion You are sorting N numbers with Radix sort. You can choose what base the numbers will be represented in within the sort procedure. What base would you choose? Why? Algorithms (580) Linear Sorting March 2018 15 / 18 Radix Sort Performance The Radix Assuming we have N numbers Expressed in base B Each with up to d digits Radix sort takes d(N + B) time. Base B has values in the range 0 to (B − 1) So, there are B distinct values to count A base that is O(N), e.g. base N, will limit the number of digits compared to some smaller base, while not dominating the time for each pass. Algorithms (580) Linear Sorting March 2018 16 / 18 Radix Sort Performance Binary Binary representation allows you to pick any power of 2 as a base very cheaply. Assuming we have N numbers Each number has b bits Split the number into digits each comprising r bits Radix Sort runs in Θ((b/r)(N + 2r )) time (if the stable sort takes Θ(N + k) time to sort values in the range 0 . . . k). Each number has b/r digits Choose r ∼ log2(N) gives ∼ N values per digit Under the assumption that b = O(log2N) the running time of Radix Sort is Θ(N). In practice, constant factors may mean that Quicksort is faster. Algorithms (580) Linear Sorting March 2018 17 / 18 Introduction Counting Sort Algorithm Operation Performance Radix Sort Algorithm The Radix Performance