Detail about Quick Sort

Explain in detail about Quick Sort

quicksort has been the fastest known generic sorting algorithm in practice. Its average running time is O(N logN). It is very fast, mainly due to a very tight and highly optimized inner loop. It has O(N2) 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 logN). It is very fast, mainly due to a very tight and highly optimized inner loop. It has O(N2) 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: S1 = {x} S − {v}|x ≤ v}, and S2 = {x ∈ S − {v}|x ≥ v}.

4. Return {quicksort(S1) followed by v followed by quicksort(S2)}.

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 S1 and the other half into S2, 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.