X hits on this document

Powerpoint document

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

76 views

0 shares

0 downloads

0 comments

10 / 28

Comp 122

linsort - 10

Lin / Devi

Comp 122

Non-comparison Sorts: Counting Sort

Depends on a key assumption: numbers to be sorted are integers in {0, 1, 2, …, k}.

Input: A[1..n] , where A[j] {0, 1, 2, …, k} for j = 1, 2, …, n. Array A and values n and k are given as parameters.

Output: B[1..n] sorted. B is assumed to be already allocated and is given as a parameter.

Auxiliary Storage: C[0..k]

Runs in linear time if   k = O(n).

Example: On board.

Document info
Document views76
Page views76
Page last viewedFri Dec 09 09:46:23 UTC 2016
Pages28
Paragraphs427
Words1924

Comments