[SOLVED] algorithm Linear Sorting

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 rangeFor j = 1 to NC [A[j ]] = C [A[j ]] + 1 <– count how many A[j] there areFor i = 1 to kC [i ] = C [i ] + C [i 1] <– how many less than or equal to iFor j = N to 1B[C [A[j ]]] = A[j ]C [A[j ]] = C [A[j ]] 1Return BAlgorithms (580) Linear Sorting March 2018 3 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort OperationCounting SortCounts of each value are saved into CNext the counts are accumulatedNow C [i ] holds number of values iFinally copy contents of A to correct positions in B using CAlgorithms (580) Linear Sorting March 2018 4 / 18Counting Sort PerformanceCounting Sort TimeCounting sort makes two passes through the input and two passes throughthe count table CSo, the time taken is …Counting Sort(Input: A = [A1, . . . ,AN ], k)For i = 0 to kC [i ] = 0 <– one entry per value in the rangeFor j = 1 to NC [A[j ]] = C [A[j ]] + 1 <– count how many A[j] there areFor i = 1 to kC [i ] = C [i ] + C [i 1] <– how many less than or equal to iFor j = N to 1B[C [A[j ]]] = A[j ]C [A[j ]] = C [A[j ]] 1Return BAlgorithms (580) Linear Sorting March 2018 5 / 18Counting Sort PerformancePropertiesCounting Sort runs in (N + k) time.QuestionUnder what circumstances does this become O(N) time?Counting Sort is also stableDifferent 3s stay in the same orderCan be important when the values are linked to other dataThis property is used by the next algorithmAlgorithms (580) Linear Sorting March 2018 6 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values535 089158 134189 158134 189840 535558 558089 840It makes d passes through the dataEach pass sorts on the ith digit onlyAlgorithms (580) Linear Sorting March 2018 7 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values535158189134840558089Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 8 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values840134535158558189089Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 9 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values840134535158558189089Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 10 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values134535840158558189089Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 11 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values134535840158558189089Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 12 / 18Radix Sort AlgorithmRadix SortRadix Sort is used to sort a set of d-digit values089134158189535558840Counter-intuitively, the first sort is on the least significant digitIt allows counting sort to be used per digit, over a much smaller rangee.g. For decimal numbers there are 10 values to sort onAlgorithms (580) Linear Sorting March 2018 13 / 18Radix Sort AlgorithmRadix SortThe algorithm is simple to stateRadix Sort(Input: A = [A1, . . . ,AN ], d)For i = 0 to dUse a stable sort to sort A on digit iCounting Sort can implement the stable sort efficientlyAlgorithms (580) Linear Sorting March 2018 14 / 18Radix Sort The RadixThe RadixRadix Sort(Input: A = [A1, . . . ,AN ], d)For i = 0 to dUse a stable sort to sort A on digit iDiscussionYou are sorting N numbers with Radix sort. You can choose what base thenumbers will be represented in within the sort procedure.What base would you choose?Why?Algorithms (580) Linear Sorting March 2018 15 / 18Radix Sort PerformanceThe RadixAssuming we have N numbersExpressed in base BEach with up to d digitsRadix sort takes d(N + B) time.Base B has values in the range 0 to (B 1)So, there are B distinct values to countA base that is O(N), e.g. base N, will limit the number of digits comparedto some smaller base, while not dominating the time for each pass.Algorithms (580) Linear Sorting March 2018 16 / 18Radix Sort PerformanceBinaryBinary representation allows you to pick any power of 2 as a base verycheaply. Assuming we have N numbersEach number has b bitsSplit the number into digits each comprising r bitsRadix 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 digitsChoose r log2(N) gives N values per digitUnder the assumption that b = O(log2N) the running time of Radix Sortis (N). In practice, constant factors may mean that Quicksort is faster.Algorithms (580) Linear Sorting March 2018 17 / 18IntroductionCounting SortAlgorithmOperationPerformanceRadix SortAlgorithmThe RadixPerformance