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.
MCQ Quiz- More efficient sorting algorithms
Google Spreadsheet Form
Related Tutorials :
Here's a Java Applet Visualization which might give you a more 'colorful' idea of what happens in Quick Sort.
Recommended books for learning Computer Science, learning high quality programming, and preparing for programming interviews:
These are the standard sources of the knowledge expected from candidates interviewing at Google, Microsoft, Facebook, Amazon and other startups and top-tier technology companies. The books by Cormen or Sedgewick (a standard part of the undergraduate curriculum) are sufficient for this part of the preparation. Google specially, loves to focus on algorithmic questions.
Tutorials on Sorting- at a glance