# 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)

- Applications of Stack in … 1131 view(s)
- Circular Linked Lists 1074 view(s)
- Attendance Management Sys… 940 view(s)
- Simple Currency Converter… 666 view(s)
- Finding Minimum, Maximum … 643 view(s)
- Implementing Stack Data S… 625 view(s)
- Recursive Factorial funct… 574 view(s)
- Graph Implementation in C… 562 view(s)
- Finding Maximum Number in… 424 view(s)
- GRASP Design Patterns 359 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