# Quick Sort Algorithm with Graphical Explanation

Quick sort is one of the fastest sorting algorithms known. It sorts O(n log n) in the average case while sorts O(n^{2}) in the worst case. But in practice, it’s quick because the worst case doesn’t happen often. This based on divide-and-conquer strategy. It takes an array A that is to be sorted. The array A[p..r] is then *partitioned* into two non-empty sub-arrays A[p..q] and A[q+1..r] where q is somewhere between p and r. All elements in A[p..q] are less than all elements in A[q+1..r]. The sub-arrays are recursively sorted by calls to quicksort algorithm. Unlike merge sort, there is no combining step. The two sub-arrays form an already-sorted array.

## Quicksort Algorithm

Quicksort(A, p, r) { if (p < r) { q = Partition(A, p, r); Quicksort(A, p, q); Quicksort(A, q+1, r); } }

Clearly, all the action takes place in the **partition()** function. It rearranges the sub-array in place. The end result is two sub-arrays and all values in first sub-array are smaller than all values in second. Partition function returns the index of the “pivot” element separating the two sub-arrays.

Partition(A, p, r) { x = A[p] q = p for(s=p+1 to r) { if(A[s] < x){ q = q + 1; swap(A[q],A[s]); } } swap(A[p],A[q]); return q; }

## Graphical Explanation of Partition Function

## Graphical Explanation of Quick Sort

*What will be the worst case for the algorithm?*

Partition is always unbalanced

*What will be the best case for the algorithm?*

Partition is perfectly balanced

*Will any particular input elicit the worst case?*

Yes, Already-sorted input

The real liability of Quicksort is that it runs in O(n^{2}) on already-sorted input. There could be two possible solutions to avoid this problem:

- Randomize the input array, OR
- Pick a random pivot element

This will ensure that no particular input can be chosen to make Quicksort run in O(n^{2}) time.

### Related Posts

- Merge Sort with Graphical explanation
- This Pointer, Static Members and destructors in C++
- Pointers, Arrays and Structures in C++
- Recursion in C++
- Selection Sort: A Graphical Explanation
- Linked lists in C++
- Operations on Binary Search Trees (BST)
- Introduction to Recursion in C++
- Inheritance in C++
- Bubble Sort: A Graphical Explanation
- Implementing Dijkstra Algorithm using Priority Queue (Heap) in C++
- Bucket Sort (Bin Sort) with Example

### Popular Posts (last 30 days)

- Attendance Management Sys… 1185 view(s)
- Graph Implementation in C… 587 view(s)
- Implementing Stack Data S… 578 view(s)
- Circular Linked Lists 524 view(s)
- Applications of Stack in … 523 view(s)
- Simple Currency Converter… 442 view(s)
- GRASP Design Patterns 328 view(s)
- Advanced Data Structures … 265 view(s)
- C++ Tutorial for Intermed… 253 view(s)
- Sockets and Network Progr… 185 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books