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

Method to add an element in circular queue, Q. Let us consider a queue is h... Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

Elaborate the symbols of abstract data type, Elaborate the symbols of abstr... Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

Define the terms - key attribute and value set, Define the terms   ... Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr

The searching technique that takes o (1) time to find a data, The searching... The searching technique that takes O (1) time to find a data is    Hashing is used to find a data

Entity relationship, what is cardinality what is cardinality

Structured programming, What do you understand by term structured programmi... What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

Dijkstras algorithm, Djikstra's algorithm (named after it is discovered by ... Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

Algorithms and flowcharts, write an algorithm and draw a flowchart to calcu... write an algorithm and draw a flowchart to calculate the perimeter and area of a circle

Explain circular queues, Circular Queues:- A more efficient queue repre... Circular Queues:- A more efficient queue representation is get by regarding the array Q(1:n) as circular. It becomes more convenient to declare the array as Q(O: n-1), when  re

Applications of shortest path algorithms, The minimum cost spanning tree ha... The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o