Quick Sort (With 3 partitions)

3-way partition algorithm

Algorithm for 3-way partition

Back to our problem

  1. The numbers a and b are our first and last elements. So our array for the algorithm is one less from both ends. If the first element is greater than the last element, they’re swapped.
  2. Once our algorithm is run, we swap our first element with the last element lesser than the first element. Last is in terms of position, not value. Similarly, the last element of the array is swapped with the first element greater than the last element. This way, we get fixed positions for the first and last elements of the array, creating 3 partitions.
  3. The same things are done with the individual 3 partitions formed by the pivots.
Modified 3-way partition algorithm

Example

Current Scenario as started
New partitions formed after 1st recursion

Time Complexity

A Case to See

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How variables behave in Python 3

Bug Hunting on Dark Web !!!

Sketch resources using Azure Blueprints

BigQuery Migration using GCP native methods

Math in Unity : create a “graphic grid” with Cartesian Plane and Line Renderer (Part I)

Download Subtitle Film Hacker 2017

Generating Dart REST API client libraries using OpenAPI Generator

How to get AWS certified in 438 days

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sohamchauhan

Sohamchauhan

More from Medium

Increasing Triplet Subsequence

Re rooting the Tree

1984. Minimum Difference Between Highest and Lowest of K Scores

Importance of Unit tests — My journey with Unit-tests 2