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
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 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     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 is    Hashing is used to find a data


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

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

write an algorithm and draw a flowchart to calculate the perimeter and area of a circle

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

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