Technical Interview Questions: Understanding Quicksort Algorithm

Technical Interview Questions: Understanding Quicksort Algorithms

The third round of interview questions wouldn’t be fair if we didn’t mention a sorting algorithm! So, in this tutorial, I decided to go through one of the most efficient sorting algorithms: The Quicksort Algorithm!

What is the Quicksort Algorithm?

Quicksort is one of the most efficient sorting algorithms and an excellent question for an interview. 

The best-case time complexity of Quicksort is O(n log n), average-case complexity is O(n log n), and O(n^2) in the worst case. So, of course, the dataset plays a significant role in the complexity of any sorting algorithm. But there is no harm in mentioning that Quicksort is considered the fastest sorting algorithm most of the time.

How Does Quicksort work? 

The Quicksort algorithm works on the principle of repeatedly dividing and conquering. It always picks an element as a pivot, splits the array of data into smaller chunks, sorts sub-arrays, and then combines them. 

Three steps of Quicksort;

Choose the pivot:

Quicksort algorithm has different implementations for pivot selection, but the aim is to choose the middle element as the pivot. Various algorithms determine the first or last item as a pivot.

Divide and conquer the data:

Based on the chosen pivot pointer, the array of items smaller than the pivot will be placed on the left side, and the array of items bigger than the pivot will be placed on the right side of the pivot. 

Combine (if needed):

Repeat the steps until all data is sorted, and then combine the sorted sub-arrays.

Quicksort Implementation in Java

The below implementation is from programcreek.com and uses the middle element of the array as a pivot and orders based on that.

public static void quickSort(int[] arr, int low, int high) {
		if (arr == null || arr.length == 0)
			return;
		if (low >= high)
			return;
		// pick the pivot
		int middle = low + (high - low) / 2;
		int pivot = arr[middle];
		// make left < pivot and right > pivot
		int i = low, j = high;
		while (i <= j) {
			while (arr[i] < pivot) {
				i++;
			}
			while (arr[j] > pivot) {
				j--;
			}
			if (i <= j) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
				j--;
			}
		}
		// recursively sort two sub parts
		if (low < j)
			quickSort(arr, low, j);
		if (high > i)
			quickSort(arr, i, high);
	}

Quicksort Algorithm Iteration for a pre-defined dataset;

Conclusion

Quicksort algorithm gives instructions about sorting a dataset in a few steps but does not restrict you with the step details. There might be different implementations for pivot selection and different swap algorithms, and even the way you combine data might be different.  In that sense feel free to check out different implementations of Quicksort. 

Exceptionly Tech Blog is a great source to keep yourself up to date as it challenges tools, best practices, and methodologies.

Check out some of my other posts that might help you with your interview preparation!

Technical Interview Questions: Sliding Window Technique

Technical Interview Questions: Binary Search Algorithm

Leave a Reply

Your email address will not be published.

#

“Exceptionly was such a fast and efficient process. Complete game changer for hiring remote.”

Liam Martin
Co-Founder at TimeDoctor

#

“Great service, outstanding speed, stunning quality.”

Andy Tryba
CEO at Gigster

Is Exceptionly an outsourcing business?

No. We encourage our clients to do direct hires. We provide payroll consultancy and services in a 100% transparent way if our clients are new to remote hiring.

Is Exceptionly a database of candidates?

Not really, data is only a small part of our business. While we own over 2 million publicly available software engineer data evaluated, our power lies in hands-on testing and engineer-to-engineer technical interviews.

Is Exceptionly expensive?

Exceptionly is more cost-efficient than any other serious competitor who owns a decent technical testing funnel. If you compare Exceptionly with HR agencies who only do resume screening before endorsement, yes, it is expensive.

Who is the founder of Exceptionly?

Sinan Ata is the founder of Exceptionly, who previously built two global technical talent acquisition enginess and tested over 2.5 million software engineers in his career.

Still have questions? Contact us.

Ready to meet top-notch engineers?

Let's get your talent pipelines up and running!

HIRE WITH EXCEPTIONLY

No hidden fees.