quicksort has been the fastest known generic sorting algorithm in practice. Its average running time is O(N logN).

**Explain in detail about Quick
Sort**

**quicksort **has been the fastest known
generic sorting algorithm in practice. Its average** **running time is *O*(*N* log*N*).
It is very fast, mainly due to a very tight and highly optimized inner loop. It
has *O*(*N*2) worst-case performance, but this can be made exponentially
unlikely with a little effort. By combining quicksort **quicksort** has historically been the fastest known generic sorting
algorithm in practice. Its average running time is *O*(*N* log*N*). It is very fast, mainly due to a
very tight and highly optimized inner loop. It has *O*(*N*2) worst-case
performance, but this can be made exponentially unlikely with a little effort.
By combining quicksort

*1 *template
<typename Comparable>

*2 *void
SORT( vector<Comparable> & items )

*3 *{

*4 *if(
items.size( ) > 1 )

*5 *{

*6 *vector<Comparable>
smaller;

*7 *vector<Comparable>
same;

*8 *vector<Comparable>
larger;

*9
*

*10 *auto
chosenItem = items[ items.size( ) / 2 ];

*11
*

*12 *for( auto
& i : items )

*13 *{

*14 *if( i
< chosenItem )

*15 *smaller.push_back(
std::move( i ) );

*16 *else if(
chosenItem < i )

*17 *larger.push_back(
std::move( i ) );

*18 *else

*19 *same.push_back(
std::move( i ) );

*20 *}

*21
*

*22 *SORT(
smaller ); // Recursive call!

*23 *SORT(
larger ); // Recursive call!

*24
*

*25 *std::move(
begin( smaller ), end( smaller ), begin( items ) );

*26 *std::move(
begin( same ), end( same ), begin( items ) + smaller.size( ) );

*27 *std::move(
begin( larger ), end( larger ), end( items ) - larger.size( ) );

*28 *}

*29 *}

**Simple recursive sorting algorithm**

respectable
on most inputs. In fact, if the list contains large numbers of duplicates with
relatively few distinct items, as is sometimes the case, then the performance
is extremely good. The algorithm we have described forms the basis of the quicksort.
However, by making the extra

lists,
and doing so recursively, it is hard to see how we have improved upon
mergesort. In fact, so far,
we really haven’t. In order to do better, we must avoid using
significant extra memory and

have
inner loops that are clean. Thus quicksort is commonly written in a manner that
avoids creating the second group (the equal items), and the algorithm has
numerous subtle details that

affect
the performance; therein lies the complications. We now describe the most
common implementation of quicksort—“classic quicksort,” in which the input is an array, and in which no

extra
arrays are created by the algorithm. The classic quicksort algorithm to sort an
array *S* consists of the following
four easy steps:

1. If the
number of elements in *S* is 0 or 1,
then return.

2. Pick any
element *v* in *S*. This is called the **pivot.**

3. **Partition ***S*** **−** **{*v*} (the remaining elements in** ***S*)
into two disjoint groups:** ***S*1 = {*x}*** ***S *−* *{*v*}|*x *≤* v*}, and* S*2 = {*x *∈* S *−* *{*v*}|*x
*≥* v*}.

4. Return
{quicksort(*S*1) followed by *v* followed by quicksort(*S*2)}.

Since the
partition step ambiguously describes what to do with elements equal to the
pivot, this becomes a design decision. Part of a good implementation is
handling this case as efficiently as possible. Intuitively, we would hope that
about half the elements that are equal to the pivot go into *S*1 and the other half into *S*2, much as we like binary search trees
to be balanced.Thefigureshows the action of quicksort on a set of numbers. The
pivot is chosen (by chance) to be 65. The remaining elements in the set are
partitioned into two smaller sets. Recursively sorting the set of smaller
numbers yields 0, 13, 26, 31, 43, 57 (by rule 3of recursion). The set of large
numbers is similarly sorted. The sorted arrangement of theentire set is then
trivially obtained.It should be clear that this algorithm works, but it is not
clear why it is any fasterthan mergesort. Like mergesort, it recursively solves
two subproblems and requires linear additional work (step 3), but, unlike
mergesort, the subproblems are not guaranteed to be of equal size, which is
potentially bad. The reason that quicksort is faster is that the partitioning
step can actually be performed in place and very efficiently. This efficiency
more than makes up for the lack of equal-sized recursive calls. The algorithm
as described so far lacks quite a few details, which we now fill in. There are
many ways to implement steps 2 and 3; the method presented here is the result of
extensive analysis and empirical study and represents a very efficient way to
implement quicksort. Even the slightest deviations from this method can cause
surprisingly bad results.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Sorting And Searching : Detail about Quick Sort |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.