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


Related Discussions:- Write the algorithm of the quick sort

Threaded binary tree, i need the full concept of it... please can anyone pr...

i need the full concept of it... please can anyone provide

State hsv colour model, HSV Colour Model Instead of a set of colour pri...

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

Multiple stack in single dimensional array, Implement multiple stacks in a ...

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

Algorithm, what algorithms can i use for the above title in my project desi...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Endogenous model, Question a) Describe how the endogenous model is an ...

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.

Linked list implementation of any circular queue, Link list representation ...

Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link

Sorted list followed by a few "random" elements, You have to sort a list L ...

You have to sort a list L having of a sorted list followed by a few "random" elements. Which sorting methods would be especially suitable for this type of task?   Insertion sort

Tree Traversal, If preorder traversal and post order traversal is given the...

If preorder traversal and post order traversal is given then how to calculate the pre order traversal. Please illustrate step by step process

Naïve recursive algorithm for binomial coefficients, How many recursive cal...

How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

The theta-notation, This notation bounds a function to in constant factors....

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd