Quicksort

0
40
Quicksort tutorial

Quicksort is a sorting algorithm that picks an element (“the pivot”) and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted – from Wikipedia.

Quicksort Basics

Time Complexity

  • O(n^2) Worst case performance
  • O(n log n) Best-case performance
  • O(n log n) Average performance

Space Complexity

  • O(log(n)) Worst case

Approach

  • Make the right-most index value pivot
  • Partition the array using pivot value
  • Quicksort left partition recursively
  • Quicksort right partition recursively

1. Lomuto partition scheme mechanism

This scheme chooses a pivot which is typically the last element in the array. The algorithm maintains the index to put the pivot in variable i and each time it finds an element less than or equal to pivot, this index is incremented and that element would be placed before the pivot.

Quick Sort mechanism:

Example of quick sort

2. Hoare partition scheme

It uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater or equal than the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index. Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.

Partition:

Quicksort Explained

Quicksort animation explained step-by-step
Quicksort animation explained step-by-step

Explained quicksort step-by-step

Video tutorial quicksort explained

Quicksort Implementation

C Implementation

C++ Implementation

Java implementation for Quicksort

Python Implementation

You may also like:

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.