Implement a linear-expected-time algorithm for selecting the kth smallest element

Algorithm description

1. If |S| = 1, then k = 1 and return the element in S as the answer.

2. Pick a pivot element, v[S]. Partition S-{v} into S1 and S2, as done with quicksort

3. If k<=|S1|, then the kth smallest element must be in S1. In this case, return quickselect(S1,k).

4. If k=1+|S1|, the pivot is the kth smallest element and return it.

5. Otherwise, the kth smallest element lies in S2, and it is the (k-|

S1|-1)st smallest element in S2, and return quickselect(S2,k-| S1|-1).

Deliverables

1. Source code, i.e. *.java file

2. Time complexity analysis

 

Posted Date: 3/14/2013 1:46:55 AM | Location : United States

Ask an Expert

Related Discussions:- linear-expected-time algorithm, Assignment Help, Ask Question on linear-expected-time algorithm, Get Answer, Expert's Help, linear-expected-time algorithm Discussions

Write discussion on linear-expected-time algorithm
Your posts are moderated

Write your message here..

Related Questions

Explain binary search tree, Binary search tree. A binary search tree is... Binary search tree. A binary search tree is a binary tree that is either empty or in which every node having a key that satisfies the following conditions: - All keys (if an

A full binary tree with n leaves, A full binary tree with n leaves have:- ... A full binary tree with n leaves have:- 2n -1 nodes.

Algorithm for binary search, Q. Write down the algorithm for binary search.... Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Methods, what is folding method? what is folding method?

Total weight of minimum spanning tree, a) Run your program for α = 0.05, 0... a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

A linear list of elements in which deletion can be done, A linear list of e... A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

Algorithm, write an algorithm given each students name and grade points for... write an algorithm given each students name and grade points for six courses.find his grade point average and group students into the gpa groups 3.5

Illustrate the visual realism applications, Illustrate the Visual realism a... Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Define stack lifo, A stack is a last in, first out (LIFO) abstract data typ... A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

Implement stack using two queues, How To implement stack using two queues ,... How To implement stack using two queues , analyze the running time of the stack operations ?