## Write the algorithm of the quick sort, Data Structure & Algorithms

Assignment Help:

Ans.

An algorithm for the quick sort is as follows:

void quicksort ( int a[ ], int lower, int upper )

{

int i ;

if ( upper > lower ) {

i = split ( a, lower, upper ) ; quicksort ( a, lower, i - 1 ) ; quicksort ( a, i + 1, upper ) ;                                }

}

int split ( int a[ ], int lower, int upper ){

int i, p, q, t ;

p = lower + 1 ;

q = upper ;

i = a[lower] ;

while ( q >= p )

{

while ( a[p] < i )

p++ ;

while ( a[q] > i )

q-- ;

if ( q > p )

{

t = a[p] ; a[p] = a[q] ; a[q] = t ;

}

}

t = a[lower] ; a[lower] = a[q] ; a[q] = t ;

return q ; }

#### How do you find the complexity of an algorithm, How do you find the complex...

How do you find the complexity of an algorithm?  Complexity of an algorithm is the measure of analysis of algorithm. Analyzing an algorithm means predicting the resources that

#### Abstract data type-tree, Definition: A set of data values & related operati...

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

#### Storing a sparse matrix in memory, Explain an efficient method of storing a...

Explain an efficient method of storing a sparse matrix in memory. Write a module to find the transpose of the sparse matrix stored in this way. A matrix which contains number o

#### Data flow diagrams, How to construct a data flow diagram for a college assi...

How to construct a data flow diagram for a college assignment and marking systemA

#### Steps of pre-order traversal, Pre-order Traversal The method of doing a...

Pre-order Traversal The method of doing a pre-order traversal iteratively then has the several steps(suppose that a stack is available to hold pointers to the appropriate nodes

#### Binary trees, A binary tree is a special tree where each non-leaf node can ...

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

#### Total weight of minimum spanning tree, a) Run your program for α = 0.05, 0...

a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

#### Time complexity, The  total  of  time  needed  by  an algorithm to run to i...

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

#### Tree, tree is graph or not

tree is graph or not

#### Algorithms for push and pop operation, Q. Suggest a method of implementing ...

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed  