Part of course:

Quick-sort: Video tutorial, pseudo-code (and in-place sorting)

- Algorithm with Example
- Algorithm Steps
- Comparison to Simple Sort
- Bonus: Performing the partition in-place
- Comparison to merge-sort (and run-time analysis)
- References

NaN.

Part of course: Competitive Programming: From Beginner to Expert

Quick-sort: Video tutorial, pseudo-code (and in-place sorting)[ Edit ]

We want to sort an array with n elements. Quick-sort does this by breaking up the array into non-overlapping segments, sorting them separately and then combining the results.

For instance, suppose we have a box with slips of paper with numbers between 100 and 300 to be sorted. We could first separate the slips into two bunches: those with values below 200 and those with values above 200. We can sort these bunches separately. Since all the values in the second bunch are larger than those in the first bunch, we can combine them easily into a single sorted bunch. [1]

The video focuses purely on the **algorithm** and *doesn't get distracted by implementation details*, which is great if you're trying to understand the algorithm for the first time.

We're given an array of length n. (*steps below assume that all elements in the array are distinct*)

def quick_sort(array)pivot = randomly chosen element from the arrayleft = all elements smaller than pivotright = all elements larger than pivotleft = quick_sort(left)right = quick_sort(right)return left + [pivot] + right

Since the algorithm is recursive (quick-sort calls quick-sort for smaller arrays), we need to have a **base case**. The base case for quick sort is that if the array is of length 1, then it is already sorted.

Naive sorting algorithms such as Simple Sort in the previous tutorial are take O(n^2) time because they **duplicate*** comparisons. *If we have n numbers, then the total number of pairs is n(n-1)/2 = O(n^2), and naive sorting algorithms compare every pair of numbers.

In quick-sort, we choose a pivot and separate the array into two parts. Once we separate the two parts, we know that **every** number in the first part is lesser than **every** number in the second part *without ever having compared them directly to each other*.

**Bonus**: An animated race between bubble-sort (similar to simple-sort) and quick-sort!

It is possible to run quick-sort *in-place*. That is, we do not need to make separate arrays which store each part. This saves memory and also makes the code faster. The first 2 minutes of the video below describe how to perform in-place partition.

In addition, you can also check-out the pseudo-code for performing in-place partition on Wikipedia.

The main advantage of quick-sort over merge sort, is that the sorting can be done in-place. This saves time because we don't have to create new arrays.

The run-time of quick-sort is same as merge-sort in the average case, i.e. O(n \log n). This is true even if we get quite bad splits of the array (say 10% on one side and 90% on the other side) each time.

The main disadvantage is that is the randomly picked pivot is bad for the first few times, then it will still take longer to execute.

Also, for those who are theoretically inclined, the algorithm has a worst-case complexity of O(n^2), although that is almost impossible if sorting more than 10 elements.

Read more…(509 words)

Mark as completed

Previous

Quiz: Recursion

Next

[ZCO15002] Variation (ZCO 2015: India)

Part of courses:

About the contributor:

Keshav DhandhaniaIOI medalist. DM me for 1-on-1 mentorship (paid).

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Quick-sort: Video tutorial, pseudo-code (and in-place sorting)

- Algorithm with Example
- Algorithm Steps
- Comparison to Simple Sort
- Bonus: Performing the partition in-place
- Comparison to merge-sort (and run-time analysis)
- References

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

About Us

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.