TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 13.4 - Goodrich, Tamassia, Goldwasser
This chapter provides knowledge of radix sort. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Bucket-Sort and Radix-Sort 3/29/14 21:33 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Bucket-Sort and Radix-Sort 1, c B ∅ 3, a ∅ 3, b ∅ ∅ ∅ 7, d 7, g 7, e ∅ ∅ 0 1 2 3 4 5 6 7 8 9 © 2014 Goodrich, Tamassia, Goldwasser Bucket-Sort and Radix-Sort 1 Bucket-Sort ! Let be S be a sequence of n ! ! (key, element) items with keys in the range [0, N - 1] Bucket-sort uses the keys as indices into an auxiliary array B of sequences (buckets) Algorithm bucketSort(S): Input: Sequence S of entries with integer keys in the range [0, N − 1] Output: Sequence S sorted in nondecreasing order of the keys let B be an array of N sequences, Phase 1: Empty sequence S by moving each entry (k, o) into its each of which is initially empty bucket B[k] for each entry e in S do k = the key of e Phase 2: For i = 0, , N - 1, move the entries of bucket B[i] to the remove e from S end of sequence S insert e at the end of bucket B[k] Analysis: for i = 0 to N−1 do n Phase 1 takes O(n) time for each entry e in B[i] do remove e from B[i] n Phase 2 takes O(n + N) time insert e at the end of S Bucket-sort takes O(n + N) time © 2014 Goodrich, Tamassia, Goldwasser Bucket-Sort and Radix-Sort 2 1 Bucket-Sort and Radix-Sort 3/29/14 21:33 Example ! Key range [0, 9] 7, d 1, c 3, a 7, g 3, b 7, e Phase 1 1, c B 3, a ∅ ∅ 0 1 2 3, b ∅ 3 ∅ ∅ 4 5 6 7, d ∅ 7, e ∅ 8 7 7, g 9 Phase 2 1, c 3, a © 2014 Goodrich, Tamassia, Goldwasser 3, b 7, d 7, g 7, e Bucket-Sort and Radix-Sort 3 Properties and Extensions ! Key-type Property n n The keys are used as indices into an array and cannot be arbitrary objects No external comparator ! Stable Sort Property n The relative order of any two items with the same key is preserved after the execution of the algorithm © 2014 Goodrich, Tamassia, Goldwasser Extensions n Integer keys in the range
đang nạp các trang xem trước
