Sorting algorithms are essential for organizing data in computer science, and QuickSort is among the most well-known and efficient of these tools. This article examines QuickSort in Python, and its algorithm, with an emphasis on recursive implementation. We will also do sorting an array using user input with it.
What is QuickSort in Python?
Quicksort is a popular sorting algorithm that sorts an array using a divide-and-conquer strategy, which implies that it sorts an array by repeatedly dividing it into smaller subarrays and then sorting the subarrays recursively.
It is one of the most effective data-sorting algorithms available. It is typically faster than other sorting algorithms such as merge sort for large arrays. In practical applications, it outperforms other sorting algorithms such as Bubble Sort and Insertion Sort despite having a worst-case time complexity of O(n^2).
The basic idea behind the QuickSort algorithm is to divide an array into two subarrays, one containing all the elements smaller than the pivot element and the other containing all the elements larger than the pivot element.
Frequently, the median of the array serves as the pivot point. After the array has been partitioned, the QuickSort algorithm sorts the two subarrays recursively. All subarrays are emptied sequentially until the entire array is sorted.
QuickSort Algorithm
Listed below are the components of the QuickSort algorithm:
- A pivot element is used to divide a larger array into subarrays.
- When dividing the array in half, the pivot should be positioned such that elements smaller than the pivot are maintained on the left and elements larger than the pivot are maintained on the right.
- The same technique is used to separate the left and right subarrays.
- This procedure is repeated until every subarray contains a single value.
- Currently, the components have been sorted. The items are finally combined into a single sorted array.
The pseudo-code for the algorithm is as follows:
quicksort(arr) if length(arr) <= 1 return arr else pivot = arr[0] left = empty array right = empty array for each element x in arr[1:] if x < pivot append x to left else append x to right sorted_left = quicksort(left) sorted_right = quicksort(right) return sorted_left + [pivot] + sorted_right
QuickSort Program in Python
The implementation begins with a test to determine whether the length of the array is less than or equal to one. In this case, the array is already sorted, so it can be returned.
If not, the first element is used as a pivot to divide the array into two parts: those with values less than or equal to the pivot, and those with values greater than or equal to the pivot. Next, we sort the subarrays recursively and join them to the pivot to create the final sorted array. This array can be sorted by passing it through the quicksort() function.
Here is the code for the implementation of QuickSort in Python:
def quicksort(arr): if len(arr) <= 1: return arr else: pivot = arr[0] left = [x for x in arr[1:] if x < pivot] right = [x for x in arr[1:] if x >= pivot] return quicksort(left) + [pivot] + quicksort(right) arr = [5, 1, 8, 3, 2] print("original array:", arr) sorted_arr = quicksort(arr) print("Sorted array:", sorted_arr)
Output:
original array: [5, 1, 8, 3, 2] Sorted array: [1, 2, 3, 5, 8]
Quicksort in Python with user input
Here the user's input, which consists of an array of integers separated by spaces, is first converted into a string. Through a string argument passed to the ‘input’ function, the user is prompted to enter the array's elements. The final step is to create an integer for each substring using a list comprehension.
We utilise the ‘quicksort’ function to sort the array. The 'print' function is then used to display the sorted array to the user.Let’s look at the code:
def quicksort(arr): if len(arr) <= 1: return arr else: pivot = arr[0] left = [x for x in arr[1:] if x < pivot] right = [x for x in arr[1:] if x >= pivot] return quicksort(left) + [pivot] + quicksort(right) user_input = input("Enter the array elements separated by spaces: ") arr = [int(x) for x in user_input.split()] sorted_arr = quicksort(arr) print("Sorted array:", sorted_arr)
Output:
Enter the array elements separated by spaces: 1 5 6 2 4 7 9 Sorted array: [1, 2, 4, 5, 6, 7, 9]
Here, we use the ‘split’ function to separate a set of substrings from the input string based on whether they contain the space character. A string can be divided into a list of substrings based on a delimiter using the split() function in Python. The delimiter can be changed from the default space character to any other character or string.
Also, check the code for Quick Sort in C++ here.
Recursion in QuickSort?
Recursion has been utilized in the above programs. The ‘quicksort’ function, a recursive function that calls itself twice, sorts the left and right halves of an array separately after partitioning it.
The following describes how the recursive algorithm works. When all 'arr' is passed to the 'quicksort' function, the array is quickly sorted, and the function returns the sorted array if the array's length is one or less.
When this isn't the case, the pivot element is selected as the array's first element, and two new arrays are made: the ‘left’ array contains all elements smaller than the pivot, and the ‘right’ array contains all elements larger than or equal to the pivot.
Recursively calling the ‘quicksort’ function with the ‘left’ and right’ sub-arrays produces a sorted array by appending the output to the pivot element. This process is repeated until the length of each subarray is 0 or 1 (when 'len(arr) = 1').
Conclusion
This is a complete guide for the Quick Sort algorithm in Python for sorting large datasets due to its speed and precision. It uses a divide-and-conquer approach that can be implemented recursive or iterative, and there are a variety of methods for determining which element will serve as the pivot. Happy Learning :)
