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
Complexity of an Algorithm An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorith

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Area Subdivision Method In this method, the viewport is examined for clear decisions on the polygons situated in it, in regard to their overlap and visibility to the viewer. Fo

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

Implementations of Kruskal's algorithm for Minimum Spanning Tree. You are implementing Kruskal's algorithm here. Please implement the array-based Union-Find data structure.

Question a) Describe how the endogenous model is an improvement to the neo-classical model in explaining the long-run effect of investment on economic growth of a country.