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
Loops There are 3 common ways of performing a looping function: for ... to ... next, while ... endwhile and repeat ... until The below example input 100 numbers and find

We have discussed already about three tree traversal methods in the earlier section on general tree. The similar three different ways to do the traversal -inorder , preorder, and p

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Gouraud Shading The faceted appearance of a Lambert shaded model is due to each polygon having only a single colour. To avoid this effect, it is necessary to vary the colour ac

Write an algorithm to print all even numbers in descending order and draw the flowchart

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part

1.Create a flowchart to show the process that will allow the implementation of Stack, Push, and Pop operations. 2.Create a flowchart to show the process that will allow the impleme

1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is