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

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 ; }

Posted Date: 7/12/2012 8:33:20 AM | Location : United States







Related Discussions:- Write the algorithm of the quick sort, Assignment Help, Ask Question on Write the algorithm of the quick sort, Get Answer, Expert's Help, Write the algorithm of the quick sort Discussions

Write discussion on Write the algorithm of the quick sort
Your posts are moderated
Related Questions
Do you have a library solution for this problem?

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

Question 1 . Give the structure of PL/SQL Blocks and explain Question 2 . Differentiate between PL/SQL functions and procedures Question 3 . Explain the following Par

Full Binary Trees: A binary tree of height h that had 2h -1 elements is called a Full Binary Tree. Complete Binary Trees: A binary tree whereby if the height is d, and all of

how multiple stacks can be implemented using one dimensional array

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

Threaded Binary Tree : If a node in a binary tree is not having left or right child or it is a leaf node then that absence of child node is shown by the null pointers. The spac

Example of Back Face Detection Method To illustrate the method, we shall start with the tetrahedron (pyramid) PQRS of     Figure with vertices P (1, 1, 2), Q (3, 2, 3), R (1,

what is folding method?