X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 21 / 28

72 views

0 shares

0 downloads

0 comments

21 / 28

Comp 122

linsort - 21

Lin / Devi

Comp 122

Bucket-Sort (A)

BucketSort(A)

1.  n length[A]

2.  for i 1 to n

3.        do insert A[i] into list B[ nA[i] ]

4.  for i 0 to n – 1

5.        do sort list B[i] with insertion sort

concatenate the lists B[i]s together in order

return the concatenated lists

Input: A[1..n], where 0 A[i] < 1 for all i.

Auxiliary array: B[0..n – 1] of linked lists, each list initially empty.

Document info
Document views72
Page views72
Page last viewedWed Dec 07 11:18:23 UTC 2016
Pages28
Paragraphs427
Words1924

Comments