Algoritma dan Struktur Data : Count Sort dan Radix Sort
Non-comparison Sort
Until now: comparison sort, the sorted order is based only on comparisons between the elements. Mergesort is asymptotically optimal θ(n lgn). No comparison sort exists that is faster by more than a constant factor. Non comparison sort can run in linear time (counting sort, radix sort, and bucket sort)
Count Sort
Count sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. For each input element x, determines the number of elements less than x
This information is being used to place element x into its correct position. Requires two other arrays : to holds the sorted output and to provides temporary working storage
Example
Pseudocode
Radix Sort
Sort a set of d-digit numbers by sorting each digits (which share the same significant position). Counterintuitively: rather on its most significant digit, sort on its least significant digit first. In order to ensure the sort works correctly, each digit sorts must be stable.
Example
Pseudocode
Which Algorithm should be used ?
How many data will you be sorting ?
- Insertion ? Quicksort ? External Sorting ?
Will there be duplicate keys in the data ?
- Stable ? Secondary key ?
What do you know about your data ?
- Already been partially sorted ?
- Distribution of the data ?
- Is it hard to compare the key ?
- Disk Access ?
How much time do you have to implement the algorithm ? Implement simple sort ?
Sumber
Slide ASD : Count Sort dan Radix Sort
Posting Komentar