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
Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

How to creat ATM project by using double linked list?

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

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.

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

algorithm of output restricted queue.

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node


an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program