Bucket Sort: Sorting Integers Sorting (Part II)

Sorting (Part II)

CSE 373 Data Structures

Unit 17

Reading: Section 3.2.6 Radix sort Section 7.6 Mergesort, Section 7.7, Quicksort, Sections 7.8 Lower bound

Bucket Sort: Sorting Integers

? Example: sort 8 numbers 3,6,7,4,11,3,9,7 all between 1 to 12.

? Step 1: scan the list and put the elements in the queues

1 2 3 4 5 6 7 8 9 10 11 12

34 3

67 7

9

11

? Step 2: concatenate the queues

3 4 6 7 9 11

3

7

3,3,4,6,7,7,9,11

? Time complexity: O(n+k).

3

Bucket Sort: Sorting Integers

? The goal: sort N numbers, all between 1 to k. ? Example: sort 8 numbers 3,6,7,4,11,3,5,7. All

between 1 to 12. ? The method: Use an array of k queues. Queue j

(for 1 j k) keeps the input numbers whose value is j. ? Each queue is denoted `a bucket'. ? Scan the list and put the elements in the buckets. ? Output the content of the buckets from 1 to k.

2

Radix Sort: Sorting integers

? Historically goes back to the 1890 census. ? Radix sort = multi-pass bucket sort of integers

in the range 0 to BP-1 ? Bucket-sort from least significant to most

significant "digit" (base B) ? Requires P(B+N) operations where P is the

number of passes (the number of base B digits in the largest possible input number). ? If P and B are constants then O(N) time to sort!

4

Radix Sort Example

Input data

478 537

9 721

3 38 123 67

After 1st pass

Bucket sort

by 1's digit

721

3

0123456789

123

721

3

123

537 478 9

537

67 38

67

478

38

9

This example uses B=10 and base 10 digits for simplicity of demonstration. Larger bucket counts should be used in an actual implementation.

5

Radix Sort Example

After 1st pass

721 3

123 537

67 478

38 9

Bucket sort by 10's digit

0123456789

03

721 537

09

123 38

67 478

After 2nd pass

3 9 721 123 537 38 67 478

6

Radix Sort Example

After 2nd pass

Bucket sort by 100's

3

digit

9

721

0123456789

123

003 123

478 537

721

537

009

38

038

67

067

478

After 3rd pass

3 9 38 67 123 478 537 721

Invariant: after k passes the low order k digits are sorted.

7

Properties of Radix Sort

? Not in-place

> needs lots of auxiliary storage.

? Stable

> equal keys always end up in same bucket in the same order.

? Fast

> Time to sort N numbers in the range 0 to BP-1 is O(P(B+N)) (P iterations, B buckets in each)

8

"Divide and Conquer"

? Very important strategy in computer science:

> Divide problem into smaller parts > Independently solve the parts > Combine these solutions to get overall solution

? Idea 1: Divide array into two halves, recursively sort left and right halves, then merge two halves Mergesort

? Idea 2 : Partition array into items that are "small" and items that are "large", then recursively sort the two sets Quicksort

9

Mergesort Example

82945316

Divide

Divide

82 9 4

Divide 8 2

9 4

5 3 1 6

5 3

1 6

1 element 8 2

94

53

16

Merge 2 8

4 9

3 5

1 6

Merge 2 4 8 9

1 3 5 6

Merge 1 2 3 4 5 6 8 9 11

Mergesort

82945316

? Divide it in two at the midpoint ? Conquer each side in turn (by

recursively sorting) ? Merge two halves together

10

Auxiliary Array

? The merging requires an auxiliary array.

24891356

Auxiliary array

12

Auxiliary Array

? The merging requires an auxiliary array.

24891356

1

Auxiliary array

13

Auxiliary Array

? The merging requires an auxiliary array.

24891356

12345

Auxiliary array

14

Merging

i

j

target

copy

i

j

target

normal

Left completed first

15

Merging

first

second i

j target

Right completed first

16

Merging

Merge(A[], T[] : integer array, left, right : integer) : { mid, i, j, k, l, target : integer; mid := (right + left)/2; i := left; j := mid + 1; target := left; while i < mid and j < right do if A[i] < A[j] then T[target] := A[i] ; i:= i + 1; else T[target] := A[j]; j := j + 1; target := target + 1; if i > mid then //left completed// for k := left to target-1 do A[k] := T[k]; if j > right then //right completed// k : = mid; l := right; while k > i do A[l] := A[k]; k := k-1; l := l-1; for k := left to target-1 do A[k] := T[k];

}

17

Recursive Mergesort

Mergesort(A[], T[] : integer array, left, right : integer) : { if left < right then mid := (left + right)/2; Mergesort(A,T,left,mid); Mergesort(A,T,mid+1,right); Merge(A,T,left,right);

}

MainMergesort(A[1..n]: integer array, n : integer) : { T[1..n]: integer array; Mergesort[A,T,1,n];

}

18

Iterative Mergesort

Merge by 1 Merge by 2 Merge by 4 Merge by 8

19

Iterative Mergesort

Need of a last copy

Merge by 1 Merge by 2 Merge by 4 Merge by 8 Merge by 16

20

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download