Skip to main content
Practice

What is Quick Sort?

Quick Sort is a sorting algorithm that works by selecting a pivot element and partitioning the array into two parts, then recursively sorting each part.


Keywords​

  • Pivot: The element used as the basis for partitioning the array.

  • Partitioning: Splitting the array into two parts based on the pivot.

  • Conquering: Sorting each of the partitioned parts individually.

  • Worst Time Complexity: O(n^2) - occurs when the array is already in reverse order.

  • Average Time Complexity: O(n log n) - in most cases, Quick Sort has logarithmic linear time complexity.


Step-by-Step Process of Quick Sort​

  1. Pivot Selection: Choose an element from the array as the pivot.

  2. Partitioning: Divide the array into two parts, placing elements smaller than the pivot to the left and larger elements to the right.

  3. Recursive Sorting: Recursively apply Quick Sort on the partitioned parts.

  4. Merging Step: Combine the sorted sub-arrays. Although Quick Sort does not have an explicit merging step, the recursively sorted parts come together to form the fully sorted array.

  5. Completion: The process concludes when all parts are sorted, yielding a completely sorted array.


Characteristics of Quick Sort​

  • Unstable Sort: Quick Sort is an unstable sorting method, meaning that the relative order of elements with equal values might change.

  • Memory Optimization: It sorts in-place, using minimal additional memory.

  • Efficient Average Performance: Quick Sort is very fast in most practical situations, with an average time complexity of O(n log n).

  • Importance of Pivot Selection: Choosing the right pivot is crucial for Quick Sort's efficiency. Generally, the median or a random element makes a good pivot.


Advantages and Disadvantages of Quick Sort​

  • Advantages: High efficiency with large datasets and minimal additional memory usage.

  • Disadvantages: Worst-case time complexity of O(n^2) and instability.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.