A few recommendations for Data Structures and Algorithms:
Quick Sort is divide and conquer algorithm like Merge Sort. Unlike Merge Sort this does not require extra space. So it sorts in place. Here dividing step is to chose a pivot and partition the array such that all elements less than or equal to pivot are to the left of it and all the elements which are greater than or equal to the pivot are to the right of it. Recursively sort the left and right parts.
The key to the algorithm is the partition procedure.
A 'partition' element is chosen. All elements less than the partition are put in the left half of the array, all elements greater than the partition are placed in the right half of the array.
The two halves are sorted independently and recursively.
1. Best case performance – When the partitioning produces two regions of size n/2 (where,
n is the total number of elements in the list) O(nlgn).
2. Worst case performance - When the partitioning produces one region of size n-1 (where,
n is the total number of elements in the list) and other of size 1 O(n2).
3. Average case – O(n(lgn))
4. It is not stable and uses O(lg(n)) extra space in the worst case.
Complete tutorial document with examples :
MCQ Quiz: Efficient Sorting Algorithms- Quick sort, Merge Sort, Heap Sort- Check how much you can score!
Your score will be e-mailed to the address filled up by you.
Related Tutorials :
Here's a Java Applet Visualization which might give you a more 'colorful' idea of what happens in Quick Sort.
Computer Science >