Quick Sort Python

Quicksort is a well-liked sorting algorithm that is frequently used. In the first half of this post, we’ll use simple integers, but we’ll show how to adapt this technique to sort objects of a custom class. Quicksort represents divide-and-conquer, in-place, and unstable sorting algorithms. Before recursively sorting the larger arrays, divide and conquer divides the array into shorter arrays until it finds an empty array, even one with only one entry. The array or any subarrays are not duplicated when used in place. However, all of the recursive calls it makes necessitate stack memory. An unstable sorting algorithm doesn’t guarantee this; it can happen, but it isn’t guaranteed. This is mostly relevant when sorting objects rather than primitive kinds.

Example 1:

We begin by choosing a pivot element. Then, to loop through all of the elements in the list, we use Python for the loop. If a number is <= to the pivot, it is shifted to the left. Otherwise, it shifts to the right side of the pivot. Our Python program returns the new high value. Item + 1 equals the new high value. After that, we must execute our algorithm. A separate procedure can be created to achieve this. This function compares the values of “low_point” and “high_point” to test if “low_pont” is less than “high_point.” We’ll be likely to progress if that’s the case. Otherwise, our sorting will come to a halt. When our sorting comes to a halt, it signifies the list has been sorted.

The prepare() method is then called by our code. This locates a pivot pointer and transfers things to their proper locations. The quicksort() method is thus called twice by our program. We use QuickSort on the pieces to the left of the pivot for the first time. For the 2nd attempt, we use QuickSort on the objects to the right of the pivot. As a result, because it calls itself, our function is recursive. Let’s now create a primary program that creates a sortable list. We begin by specifying a set of values to sort. The Python len() function is used to determine the length of our set of attributes. After that, the quicksort() method is applied.

Here you can see that the data is sorted.

Example 2:

We’ll use two functions in this example: partition() and quicksort (). The quicksort() function partitions the collection first, then calls itself recursively on the partitioned pieces. First, let’s look at the division() function. The pivot was set first, as you can see in the code. If the value we’re viewing right now is higher than the pivot. We can move on to the next piece on the left because it’s on the right side of the pivot. We must also ensure that we have not passed the low pointer, which indicates that all elements have been moved to the correct side of the pivot. After that, the method opposite to the one above is carried out. We’ve either found an out-of-order number for both high_point and low_point, or low_point is greater than high_point, in which case we’ll leave the loop. Finally, let’s put the quicksort() code into action. We can use quicksort() on a basic array to implement both functions (partition and quicksort).

This is the result. There’s no guarantee that these two 22s were in this order because the method is unstable. Maybe they were switched at first, but that doesn’t imply anything in an integer array.

Example 3:

We’re going to sort custom objects in this example. There are several different ways to extend this algorithm to sort custom objects in Python. The comparison operators for a specific class might be implemented in a Pythonic style, which means we wouldn’t have to change the algorithm because >, ==, =, etc., would work the best on our class object. One more option is to have the caller provide our algorithm with a method, which would then be utilized to perform the actual item comparison. It’s pretty simple to rewrite the algorithm for usage with bespoke objects. However, keep in mind that the algorithm isn’t completely stable. Let’s begin with the Student class. This class has only two characteristics: the student’s name and age. We’ll sort by age, which we’ll accomplish by giving the sorting algorithm a new lambda function. But first, let’s look at how this function is used in the algorithm. Instead of using the = or >= operators to make a direct comparison, we use the function to determine which student is older. Lambda transmits the object compared to the rapid sort call, which does the exact age attribute comparison.

Here you can see the sorted list of names.

Conclusion:

An array is subdivided using the Python QuickSort algorithm and then sort each entry in the list; this method calls these sub arrays repeatedly. We have gone through this concept in-depth with examples in this article.