X hits on this document

Powerpoint document

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

110 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 views110
Page views110
Page last viewedTue Jan 24 16:14:02 UTC 2017
Pages28
Paragraphs427
Words1924

Comments