linear-expected-time algorithm, Data Structure & Algorithms

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







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
Related Questions
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 have:- 2n -1 nodes.

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?

what is folding method?

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 from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

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 a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

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

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