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
for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Explain the bubble sort algorithm. Answer This algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at an insta

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

1. Start 2. Get h 3. If h T=288.15+(h*-0.0065) 4. else if h T=216.65 5. else if h T=216.65+(h*0.001) 6. else if h T=228.65+(h*0.0028) 7. else if h T=270.65 8.

A shop sells books, magazines and maps. Every item is identified by a unique 4 - digit code. All books have a code which starts with 1, all maps have a code starting with 2 and all

Tree is dynamic data structures. Trees can expand & contract as the program executes and are implemented via pointers. A tree deallocates memory whereas an element is deleted.

infix to revrse polish

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

Advantages of First in First out (FIFO) Costing Advantages claimed for first in first  out (FIFO)  costing method are: 1. Materials used are drawn from the cost record in