Sorting algorithm 2

Question

An in-place algorithm with O(n) running time that rearranges an unsorted array A[0 . . . n − 1] filled with distinct integers so that, for a given k (1<=k<=n), A[0 . . . k − 1] contains the k smallest integers in increasing order.

Is there an existing algorithm that meets these specifications, or one that can be altered to meet them?

yes, partially, the homework requires the implementation of this algorithm but the professor said in class that the algorithm already exists, I just need to know which one it is, then I can study it and implement it, can you help? — fmunshi
– fmunshi, Commented Oct 20, 2010 at 17:13

wkl · Accepted Answer · 2010-10-20 16:44:08Z

2

If you google for O(n) sorts, you would end up with Counting Sort or Radix Sort.

answered Oct 20, 2010 at 16:44

wkl

80.4k16 gold badges171 silver badges178 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Sorting algorithm 2

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related