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

Draws a rectangular grid algorithms, Prepare a GUI called Hotplate GUI that...

Prepare a GUI called Hotplate GUI that holds a central panel that draws a rectangular grid that represents Element objects which should be held in a 2-dimensional array. The applic

Explain the abstract data type assertions, Explain the Abstract data type a...

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

A Booth''s, Draw a flowchart of a Booth''s multiplication algorithm and exp...

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Illustrate trivariate colour models, Illustrate Trivariate Colour Models ...

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi

Which sorting algorithms not have running time of o (n2), Which sorting al...

Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

Depth first search and breadth first search, Q. Illustrate the result of ru...

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

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

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Algorithm and flow chart, algorithm and flow chart to find weather the give...

algorithm and flow chart to find weather the given numbers are positive or negative or neutral

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