Partition Problem. Well, that’s a very common problem that may be even asked at a lot of tech interviews — especially among Software Engineers.
Knowing how to solve this problem (by writing our “Coolest Partition Algorithm”) — will take us a step closer to solving much more complicated problems by using more complicated algorithms (for example, the famous QuickSort Algorithm, right?).
So what is the “problem”?
Before talking about the solution — let’s first of all properly define the problem. So the “Partition Problem” is given as:
Suppose you’re given a collection of elements (unsorted). And your goal is to pick one element (from this collection) and “put it in it’s correct position”.
For simplicity, let’s say that it’s “correct position” (of the picked element) is defined as a position that all smaller elements will be on its left and all greater elements will be on its right.
Meaning, we’re simply taking some collection of elements (for example, you may be familiar with “arrays” or “tuples”) and then partitioning (or splitting!) this collection into two parts — left part and right part.
The partition should be done in such a way that after it’s completed — we will be able to distinguish between the right side and the left side (based on some rule/criteria).
We can say that all elements on the left of some point are smaller than all elements on the right of that point.
Partition Algorithm [Step by Step]
Now, once we know what is the Partition Problem, let’s try to solve it by writing a suitable algorithm that can solve it.
Our Algorithm is just some “steps” to be taken, such that after they’re taken — we know that the chosen pivot is at it’s correct position (as previously explained).
Step 1: Get our collection of elements
There is a given collection of elements (numbers, etc) on which we would like to apply the “Partition Algorithm”.
Step 2: Choosing a PIVOT
Pick an element (the PIVOT) from the given collection of elements.
This PIVOT will be used for splitting the array into parts (smaller than the pivot and greater than pivot).
Usually, we’ll pick the pivot as the first element (leftmost element) of a given collection.
*pivot* — an arbitrary element of a given collection that we would like to put in it’s correct position.
Step 3: Set up “left” and “right” cursors
At this step, we will define 2 cursors/indicators which will help us in implementing this algorithm.
“left cursor” — will indicate the “leftmost” element of a given collection.
“right cursor” — will indicate the “rightmost” element of a given collection.
Step 4: Move “right cursor” to the left
Move the right cursor from its current position to the left (one step at a time) — until the element that the cursor points to is smaller than the pivot.
Simply, move the right cursor to the left until you see the first element which is smaller than the PIVOT.
Once you see such an element — STOP there(!) and move on to the next step (Step 5).
Note: If at any time during this Step 4 the “right” and “left” cursors overlap — jump to Step 7.
Step 5: Move “left cursor” to the right
Move the left cursor to the right (one step at a time) — until the element that the cursor points to is greater than the pivot.
Moving the left cursor to the right until we encounter with such an element that is greater than the PIVOT.
Once you see such an element — STOP there(!) and proceed for the next step (Step 6).
Note: If at any time during this Step 4 the “right” and “left” cursors overlap — jump to Step 7.
Step 6: Swap between “right” and “left” elements
Once the “right cursor” points to the element smaller than the pivot and the “left cursor” points to the element greater than the pivot — SWAP between these two elements.
So now, after the swap operation, on the “right side”, where the “right cursor” points to — will be the element greater than the pivot and vice versa.
Just to remind, we follow these “Step4”, “Step5” and the “swap” operation in order to “keep” all greater elements (than the pivot) on the right and all smaller elements (than the pivot) on the left.
Once this step (step 6) is complete — REPEAT the process from Step 4
Step 7: Final Step — Swap with the Pivot
This is the final step of the “Partition Algorithm”.
You should come to this step only when the “right cursor” points to the same element as the “left cursor” — meaning the “left” and “right” overlap.
At this moment, both “right” and “left” cursors point to the same element — meaning we’ve checked all the elements of the collection.
Now we would like to use the “swap” operation for the last time to complete this algorithm.
So we’ll swap between the PIVOT and the element both of the cursors point to.
Done!
After you’ve successfully completed Step 7 — you should see that the pivot is exactly at its correct position:
All elements on the left of the pivot — smaller than the pivot.
All elements on the right of the pivot — greater than the pivot.
And that’s exactly what we wanted to achieve using the “Partition Algorithm”!
Hooray!!! :)))
If you’ve come this far, I’m pretty sure you would also like to watch my video on my YouTube channel where I give the “Partition Algorithm” as an example of an Interview Question asked by Facebook.
Time and Space Complexities of Partition Algorithm
Here comes the “most fun” part, right?
After getting the idea of what is a “Partition Algorithm” and observing all of its “steps” — let’s take a quick look at it’s Time and Space Complexity.
First of all, it’s easy to notice that this algorithm does not require any additional memory space.
We didn’t use any “temporary elements” or any other collections for solving this algorithm.
We simply have been working with the same given collection. Thus we can say:
Space complexity of Partition Algorithm is — O(1). Which is great!
Regarding Time Complexity, if we’re to say that the size of the given collection is “n” — so we can see that during the partition algorithm we’ve passed through all of these “n” elements just once.
So, in this case, we can deduce that:
Time complexity of Partition Algorithm is— O(n). Because we have to go over all the “n” elements of a given collection (but just once!).
Summary
To summarize the results — we can see that the “Partition Algorithm” picks some pivot and “partitions” the given collection around this partition. It is done in such a way that after applying this “Partition Algorithm” —
all elements smaller than the pivot will be on it’s left side
all elements greater than the pivot will be on it’s right side
This “simple” algorithm is used as a core for more complex algorithms and for solving much more complicated questions, for example:
- Quick Sort Algorithm.
- Finding the kth smallest/largest element.
- Calculating the sum of “k” smallest elements within a collection.
- and much more!
So thank you guys for reading this post!
I would like to know your thoughts in the comments below!
Did it help you? What would you improve?
And also, if you’re a programmer, in what programming language are you planning to implement these steps? :)
